2024/10/06 by Aryan Sanghi, Sanghi, Aryan, Devsi Bantva +3
Computer Science · Engineering · Mathematics · #05C75 #05C76 #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Computer science #Discrete Mathematics (cs.DM) #Economics #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Graph Labeling and Dimension Problems #Line (geometry) #Mathematics #Order (exchange) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2410.04607
openalex publication_date 2024/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a simple finite connected graph. The line graph L(G) of graph G is the graph whose vertices are the edges of G, where ef ∈ E(L(G)) when e ∩ f ≠ ∅. Iteratively, the higher order line graphs are defined inductively as L1(G) = L(G) and Ln(G) = L(Ln-1(G)) for n ≥ 2. In [Derived graphs and digraphs, Beitrage zur Graphentheorie (Teubner, Leipzig 1968), 17--33 (1968)], Beineke characterize line graphs in terms of nine forbidden subgraphs. Inspired by this result, in this paper, we characterize second order line graphs in terms of pure forbidden induced subgraphs. We also give a sufficient list of forbidden subgraphs for a graph G such that G is a higher order line graph. We characterize all order line graphs of graph G with Δ(G) = 3 and 4.