Line Graphs of Multigraphs and the Forbidden Graph E6

ABSTRACT

The line graph of a multigraph is the graph whose vertices are the edges of , where two such edges are adjacent if and only if they meet in a single vertex of . We provide several characterizations of such line graphs and in particular show that a graph is a line graph if and only if it does not contain one of the 32 graphs, all of which correspond to bases of nonisotropic vectors of a six‐dimensional quadratic geometry of −‐type over a field with two elements, or, equivalently, to sets of six generating reflections in the Weyl group of type . Beineke's well‐known characterization of line graphs of ordinary graphs by nine forbidden subgraphs is a special case of our result, just as the characterization of generalized line graphs by 31 forbidden subgraphs by Cvetković, Doob, and Simić.