Beineke Graphs


A simple graph is a line graph of some simple graph iff if does not contain any of the above nine graphs, known in this work as Beineke graphs, as a forbidden induced subgraph (van Rooij and Wilf 1965; Beineke 1968; Beineke 1970; Skiena 1990, p. 138; Harary 1994, pp. 74-75; West 2000, p. 282; Gross and Yellen 2006, p. 405). This statement is sometimes known as the Beineke theorem. These nine graphs are implemented in the Wolfram Language as GraphData["Beineke"]. Of the nine, one has four nodes (the claw graph = star graph S_4 = complete bipartite graph K_(1,3)), two have five nodes, and six have six nodes (including the wheel graph W_6).

A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the six Metelsky graphs as a forbidden induced subgraph (Metelsky and Tyshkevich 1997).

See also

Forbidden Induced Subgraph, Line Graph, Metelsky Graphs, Šoltes Graphs

Explore with Wolfram|Alpha


Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.Beineke, L. W. "Characterizations of Derived Graphs." J. Combin. Th. 9, 129-135, 1970.Chartrand, G. "On Hamiltonian Line Graphs." Trans. Amer. Math. Soc. 134, 559-566, 1968.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 20 and 265, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Metelsky, Yu. and Tyshkevich, R. "On Line Graphs of Linear 3-Uniform Hypergraphs." J. Graph Th. 25, 243-251, 1997.Skiena, S. "Line Graph." §4.1.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 128 and 135-139, 1990.van Rooij, A. and Wilf, H. "The Interchange Graph of a Finite Graph." Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965.West, D. B. "Characterizing Line Graphs." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 279-282, 2000.

Cite this as:

Weisstein, Eric W. "Beineke Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications