Line Graphs of Multigraphs and the Forbidden Graph E6
Journal of Graph Theory · 31.07.2026
DOI: 10.1002/jgt.70104 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 31.07.2026. Verfasst von Hans Cuypers. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
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ć.
Zitieren
APA
Cuypers, H. (2026). Line Graphs of Multigraphs and the Forbidden Graph E6. Journal of Graph Theory. https://doi.org/10.1002/jgt.70104
Vancouver
Cuypers H. Line Graphs of Multigraphs and the Forbidden Graph E6. Journal of Graph Theory. 2026. doi:10.1002/jgt.70104
BibTeX
@article{Cuypers2026,
author = {Cuypers, Hans},
title = {Line Graphs of Multigraphs and the Forbidden Graph E6},
journal = {Journal of Graph Theory},
year = {2026},
doi = {10.1002/jgt.70104}
}
EUVIMED