Adjacent Line Graphs: Combinatorial Bounds and Structural Properties
DOI:
https://doi.org/10.29304/jqcsm.2026.18.12599Keywords:
Adjacent line graph, independence number, chromatic number, Hamilton graph, combinatorial bounds, and network modeling.Abstract
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.
Downloads
References
A. Muntaner-Batle and Y. Takahashi, "On the strength and independence number of graphs," Contrib. Math., vol. 6, pp. 25–29, 2022.
Z. Dong and Z. Wu, "On the stability of the graph independence number," SIAM Journal on Discrete Mathematics, vol. 36, no. 1, pp. 229–240, 2022.
M. J. A. Schuez, J. K. Brubaker, and H. G. Klatzgraber, "Combinatorial optimization with physics-inspired graph neural networks," Nature Machine Intelligence, vol. 4, no. 4, pp. 367–377, 2022.
A. Grzesik et al., "Polynomial-time algorithm for maximum weight independent set on P6-free graphs," ACM Transactions on Algorithms, vol. 18, no. 1, pp. 1–57, 2022.
M. Kim et al., "Rydberg quantum wires for maximum independent set problems," Nature Physics, vol. 18, no. 7, pp. 755–759, 2022.
S. Ebadi et al., "Quantum optimization of maximum independent set using Rydberg atom arrays," Science, vol. 376, no. 6598, pp. 1209–1215, 2022.
X. Wang et al., "Learning intents behind interactions with knowledge graph for recommendation," in Proceedings of the Web Conference (WWW '21), 2021, pp. 878–887.
S. Wang and W. Zhang, "Independence number, minimum degree and path-factors in graphs," Proceedings of the Romanian Academy, Series A, vol. 23, no. 3, pp. 229–234, 2022.
F. P. Dewi et al., "Game chromatic number class graphs ($C_m odot K_n$) and ($S_m odot K_n$) of corona operation result," in AIP Conference Proceedings, vol. 3046, no. 1, 2024.
Z. Masih and M. Zaker, "Some comparative results concerning the Grundy and b-chromatic number of graphs," Discrete Applied Mathematics, vol. 306, pp. 1–6, 2022.
A. Heckel and O. Riordan, "How does the chromatic number of a random graph vary?," Journal of the London Mathematical Society, vol. 108, no. 5, pp. 1769–1815, 2023.
G. Bacsó et al., "The robust chromatic number of graphs," Graphs and Combinatorics, vol. 40, no. 4, art. no. 89, 2024.
S. Pirzada and S. Khan, "On distance Laplacian spectral radius and chromatic number of graphs," Linear Algebra and its Applications, vol. 625, pp. 44–54, 2021.
S. Akbari et al., "On the chromatic vertex stability number of graphs," European Journal of Combinatorics, vol. 102, art. no. 103504, 2022.
V. Dujmović et al., "Adjacency labelling for planar graphs (and beyond)," Journal of the ACM, vol. 68, no. 6, pp. 1–33, 2021.
Manisha, P. Parveen, and J. Kumar, "Line graph characterization of the order supergraph of a finite group," Communications in Combinatorics and Optimization, 2024.
X. Lv, B. Deng, and X. Li, "On the borderenergeticity of line graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 87, pp. 693–702, 2022.
L. W. Beineke and J. S. Bagga, Line Graphs and Line Digraphs. Switzerland: Springer, 2021.
R. K. Thumbakara, G. Bobin, and J. Jose, "Subdivision graph, power and line graph of a soft graph," Communications in Mathematics and Applications, vol. 13, no. 1, pp. 75–89, 2022.
T. Abrishami et al., "Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree," Journal of Combinatorial Theory, Series B, vol. 164, pp. 371–403, 2024.
L. Ni, P. Manman, and W. Qiang, "A spectral clustering algorithm for non-linear graph embedding in information networks," Applied Sciences, vol. 14, no. 11, art. no. 4946, 2024.
M. Keçeci, "A novel tool for graph theory education: Interactive exploration of the Hamiltonian problem with Z3 and the Keçeci layout," Open Science Articles, Zenodo, 2025.
N. Behague, D. Chakraborti, and J. León, "Colour-biased Hamilton cycles in dense graphs and random graphs," arXiv preprint arXiv:2509.18012, 2025.
F. Harary, Graph Theory. Reading, MA, USA: Addison-Wesley, 1969.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. New York: North-Holland, 1979.
D. B. West, Introduction to Graph Theory, 2nd ed. Upper Saddle River, NJ, USA: Prentice Hall, 2001.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Karrar Khudhair Obayes, Ghadeer Khudhair Obayes
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
