The term "Beineke graphs" is used in this work for the nine graphs illustrated above. A simple graph is a line
graph of some simple graph iff
it contains none of the 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 
= complete bipartite
graph 
),
two have five nodes, and six have six nodes
(including the wheel graph 
).
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
References
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.House of Graphs. Beineke
Graphs. Claw Graph (K1,3), K4 with One Subdivided Edge, K3
+ 2K1, Beineke Non-Line Graph
G4, Beineke Non-Line Graph G5,
K2 + 2K2, Beineke
Non-Line Graph G7, Square of
P6, and Wheel W6.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.Referenced on Wolfram|Alpha
Beineke Graphs
Cite this as:
Weisstein, Eric W. "Beineke Graphs." From
MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BeinekeGraphs.html
Subject classifications
