Metelsky Graphs


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


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.

Subject classifications