2021/05/18 by Hans Cuypers, Cuypers, Hans
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.2105.08610
arxiv created 2021/05/18 · openalex publication_date 2021/05/18 · arxiv updated 2021/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02
Whitney's Theorem states that every graph, different from K3 or K1,3, is uniquely determined by its line graph. A 1-line graph of a multi-graph is the graph with as vertices the edges of the multi-graph, and two edges adjacent if and only if there is a unique vertex on both edges. The ≥ 1-line graph of a multi-graph is the graph on the edges of the multi-graph, where two edges are adjacent if and only if there is at least one vertex on both edges. We extend Whitney's theorem to such line graphs of multi-graphs, and show that most multi-graphs are uniquely determined by their line graph. Moreover, we present an algorithm to determine for a given graph Γ, if possible, a multi-graph with Γ as line graph.