A simple graph is a line graph of some simple graphiff
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 = complete bipartite
graph),
two have five nodes, and six have six nodes (including the wheel
graph).
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.
= complete bipartite
graph 
),
two have five nodes, and six have six nodes (including the wheel
graph 
).
