Whitney’s theorem for line graphs of multi-graphs
Abstract
Whitney’s Theorem states that every connected graph, different from K3 or K1,3, is uniquely determined by its line graph. The graphs K1,3 and K3 have isomorphic line graphs. We provide an analogue of Whitney’s Theorem for line graphs of multi-graphs. There are two obvious choices for the definition of a line graph of a multi-graph. A 1-line graph of a multi-graph is the graph with as vertices the edges of the multi-graph, and two edges adjacent if and only if there is a unique vertex which is on both edges. The ≥ 1-line graph of a multi-graph is the graph on the edges of the multi-graph, where two edges are adjacent if and only if there is at least one vertex which is on both edges. We extend Whitney’s Theorem to both classes of line graphs of multi-graphs, and show that most multi-graphs are uniquely determined by their line graph. Moreover, we present an algorithm to determine for a given graph Γ, if possible, a multi-graph with Γ as line graph.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.14
References
J.C. Bermond and J.C. Meyer, Graphe représentatif des arêtes d’un multi-graphe, J. Math. Pures Appl. 52 (1973), 299–308.
A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular graphs, volume 18 of Ergeb. Math. Grenzgeb., 3.Folge (1989), Berlin etc., Springer-Verlag.
P.J. Cameron, J.M. Goethals, J.J. Seidel, and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), 305–327.
P.J. Cameron, A note on generalized line graphs. J. Graph Theory 4 (1980), 243–245.
H. Cuypers, Line graphs of multi-graphs and the forbidden graph E6, J. Graph Theory, to appear. (https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.70104)
D. Cvetković, P. Rowlinson, and S. Simić, Spectral generalizations of line graphs, On graphs with least eigenvalue −2, volume 314 of London Mathematical Society Lecture Note Series (2004), Cambridge University Press, Cambridge.
M. Habib, C. Paul, and L. Viennot, A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata, in STACS 98 (Paris, 1998), volume 1373 of Lecture Notes in Comput. Sci. 25–38 (1998), Springer, Berlin.
R.L. Hemminger, Isomorphism-induced line isomorphisms on pseudographs, Czechoslovak Math. J. 21 (1971), 672–679.
H.A. Jung, Zu einem Isomorphiesatz von H. Whitney für Graphen, Math. Ann. 164 (1966), 270–271.
Philippe G.H. Lehot, An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comput. Mach. 21 (1974), 569–575.
D. Liu, S. Trajanovski, and P. Van Mieghem, ILIGRA: an efficient inverse line graph algorithm, J. Math. Model. Algorithms Oper. Res. 14 (2015), 13–33.
J. Naor and M.B. Novick, An efficient reconstruction of a graph from its line graph in parallel, J. Algorithms 11 (1990), 132–143.
N.D. Roussopoulos, A max {m, n} algorithm for determining the graph H from its line graph G, Information Processing Lett. 2 (1973), 108–112.
S.K. Simić, An algorithm to recognize a generalized line graph and output its root graph, Publ. Inst. Math. (Beograd) (N.S.) 49 (1991), 21–26.
H. Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), 150–168.
I.È. Zverovich, An analogue of the Whitney theorem for edge graphs of multi-graphs, and edge multigraphs, Diskret. Mat. 9 (1997), 98–105.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.