Adjacent Line Graphs: Combinatorial Bounds and Structural Properties: - Karrar Khudhair Obayes; Ghadeer Khudhair Obayes (Journal of Al-Qadisiyah for Computer Science and Mathematics, 2026)
The adjacent line graph of a graph G is defined as the graph whose vertices correspond to the edges of . Two vertices e and f are adjacent in if and only if the distance between their corresponding edges in G is at most one. Formally, for edges e and f, the adjacency condition is: is adjacent to in ⇔ ≤ 1 where is the minimum distance between any pair of their endpoints in G. This paper establishes new tight upper bounds for the independence number and chromatic number for several fundamental classes of graphs, including paths , cycles ​, and complete bipartite graphs . We present rigorous theoretical proofs for these bounds, correct previous inaccuracies in edge-count formulas, and derive important structural properties, including results on the Hamiltonicity of adjacent line graphs. The findings contribute to a deeper understanding of the combinatorial structure of and its applications in network interference modeling, channel assignment, and coding theory.