×

Graphoidal graphs and graphoidal digraphs: a generalization of line graphs. (English) Zbl 1471.05038

Summary: A graphoidal cover of a graph \(G\) is a collection \(\psi \) of paths (not necessarily open) in \(G\) such that each path in \(\psi \) has at least two vertices, every vertex of \(G\) is an internal vertex of at most one path in \(\psi \), and every edge of \(G\) is in exactly one path in \(\psi \). Let \(\Omega (\psi )\) denote the intersection graph of \(\psi \). A graph \(H\) is called a graphoidal graph if there exists a graph \(G\) and a graphoidal cover \(\psi \) of \(G\) such that \(H\) is isomorphic to \(\Omega (\psi )\). Graphoidal covers of digraphs can be similarly defined. In this article, we present a survey of known results on graphoidal graphs. We also introduce the concept of graphoidal digraphs, provide some results, and discuss several problems for further investigation.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C76 Graph operations (line graphs, products, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Acharya, B. D.; Sampathkumar, E., Graphoidal covers and graphoidal covering number of a graph, Indian J. Pure Appl. Math., 18, 10, 882-890 (1987) · Zbl 0623.05042
[2] Arumugam, S., Acharya, B. D, Sampathkumar, E. (1996). Graphoidal covers of a graph - A creative review. Proceedings of the National Workshop on Graph Theory and Its Applications, Manonmaniam Sundaranar University, Tirunelveli. Eds. S. Arumugam, B. D. Acharya and E. Sampathkumar, Tata McGraw Hill, pp. 1-28.
[3] Arumugam, S.; Pakkiam, C., Graphoidal bipartite graphs, Graphs Combin., 10, 2-4, 305-310 (1994) · Zbl 0813.05056
[4] Arumugam, S.; Pakkiam, C., The graphoidal covering number of a digraph, J. Math. Phys. Sci., 29, 33-41 (1995) · Zbl 0837.05091
[5] Arumugam, S., Rajasingh, I., Bharathi, R., Pushpam, P. R. L. (1996). On graphs whose graphoidal covering number is one less than its cyclomatic number. Proceedings of the National Workshop on Graph Theory and Its Applications, Manonmaniam Sundaranar University, Tirunelveli. Eds. S. Arumugam, B. D. Acharya and E. Sampathkumar, Tata McGraw Hill, pp. 29-34.
[6] Arumugam, S.; Rajasingh, I.; Pushpam, P. R. L., Graphs whose acyclic graphoidal covering number is one less than its maximum degree, Discrete Math., 240, 1-3, 231-237 (2001) · Zbl 0988.05079
[7] Arumugam, S.; Rajasingh, I.; Pushpam, P. R. L., A note on the graphoidal covering number of a graph, J. Discrete Math. Sci. Cryptogr., 5, 2, 145-150 (2002) · Zbl 1012.05132
[8] Arumugam, S.; Rajasingh, I.; Pushpam, P. R. L., On graphs whose acyclic graphoidal covering number is one less than its cyclomatic number, Ars Combin., 72, 255-261 (2004) · Zbl 1073.05560
[9] Arumugam, S.; Suseela, J. S., Acyclic graphoidal covers and path partitions in a graph, Discrete Math., 190, 1-3, 67-77 (1998) · Zbl 0956.05086
[10] Arumugam, S.; Suseela, J. S., On graphoidal graphs, J. Discrete Math. Sci. Cryptogr., 5, 131-137 (2002) · Zbl 1002.05056
[11] Beineke, L. W., Characterization of derived graphs, J. Combin. Theory, 9, 2, 129-135 (1970) · Zbl 0202.55702
[12] Beineke, L. W.; Bagga, J. S., Line Graphs and Line Digraphs, London, UK: Springer · Zbl 0434.05056
[13] Broersma, H. J.; Hoede, C., Path graphs, J. Graph Theory, 13, 4, 427-444 (1989) · Zbl 0677.05068
[14] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs (2016), Boca Raton, FL: CRC Press
[15] Pakkiam, C.; Arumugam, S., On the graphoidal covering number of a graph, Indian J. Pure Appl. Math., 20, 4, 330-333 (1989) · Zbl 0673.05080
[16] Pakkiam, C.; Arumugam, S., The graphoidal graphs of a tree, Indian J. Pure Appl. Math., 21, 1055-1058 (1990) · Zbl 0719.05025
[17] Pakkiam, C.; Arumugam, S., The graphoidal covering number of unicyclic graphs, Indian J. Pure Appl. Math., 23, 2, 141-143 (1992) · Zbl 0768.05079
[18] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 1, 150-168 (1932) · JFM 58.0609.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.