Image:Forbidden-line-subgraphs.png

From Wikipedia, the free encyclopedia

Image
File history
File links

Forbidden-line-subgraphs.png‎ (15KB, MIME type: image/png)

[edit] Summary

Nine minimal graphs that are not line graphs, as identified by Beineke (1968, 1970). A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.

[edit] Licensing

I, the creator of this work, hereby release it into the public domain. This applies worldwide.
In case this is not legally possible,
I grant any entity the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

File history

Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version.
Click on date to download the file or see the image uploaded on that date.

(del) (cur) 05:49, 3 November 2006 . . David Eppstein (Talk | contribs) . . 702×567 (15,169 bytes) (Nine minimal graphs that are not line graphs, as identified by Beineke (1968, 1970). A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.)