A graph with minimum vertex degree at least 5 is a line graph iff it does
not contain any of the above six graphs, known in this work as Metelsky graphs, as
an induced subgraph (Metelsky and Tyshkevich
1997). These six graphs are implemented in the Wolfram
Language as GraphData["Metelsky"].
See also
Beineke Graphs,
Forbidden
Induced Subgraph,
Line Graph
Explore with Wolfram|Alpha
References
Metelsky, Yu. and Tyshkevich, R. "On Line Graphs of
Linear 3-Uniform Hypergraphs." J. Graph Th. 25, 243-251, 1997.
Cite this as:
Weisstein, Eric W. "Metelsky Graphs."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MetelskyGraphs.html
Subject classifications
