Metelsky Graphs


As part of a more general categorization of the class of line graphs of linear 3-uniform hypergraphs with minimum vertex degree at least 19, Metelsky and Tyshkevich (1997) established that a graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of a subset of 6 of the Beineke graphs as an induced subgraph.

These graphs, illustrated above, are known in this work as Metelsky graphs and are implemented in the Wolfram Language as GraphData["Metelsky"].

See also

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

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