ON DETERMINING THE DISTANCE SPECTRUM OF A CLASS OF DISTANCE INTEGRAL GRAPHS

Document Type : Original Manuscript

Authors

Department of Mathematics, Lorestan University, Khorramabad, Iran.

Abstract

The distance eigenvalues of a connected graph G are the eigenvalues of its distance matrix‎
D(G)‎. ‎A graph is called distance integral if all of its‎
‎distance eigenvalues are integers.‎
‎Let n and k be integers with n>2k,k1‎. ‎The bipartite Kneser graph H(n,k) is the graph with the set of all k and nk subsets of the set [n]={1,2,...,n} as vertices‎, ‎in which two vertices are adjacent if and only if one of them is a subset of the other‎.
‎In this paper‎, ‎we determine the distance spectrum of H(n,1)‎. ‎Although the obtained result is not new \cite{12}‎, ‎but our proof is new‎. ‎The main tool that we use in our work is the orbit partition method in algebraic graph theory for finding the eigenvalues of graphs‎. ‎We introduce a new method for‎
‎determining the distance spectrum of H(n,1) and show how‎
‎a quotient matrix can contain all distance eigenvalues of‎
‎a graph.‎

Keywords


[1] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2012.
[2] D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the theory of graph spectra, Cambridge University Press, 2010.
[3] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
[4] L. Lu and Q. Huang, Distance eigenvalues of B(n; k), Linear and Multilinear Algebra, 69(11) (2019), 2078–2092.
[5] S. M. Mirafzal and A. Zafari, Some algebraic properties of bipartite Kneser graphs, arXiv preprint, arXiv:1804.04570, 2018.
[6] S. M. Mirafzal, A new class of integral graphs constructed from the hypercube, Linear Algebra Appl., 558 (2018), 186–194.
[7] S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proceedings-Mathematical Sciences, 129(3) (2019), 1–8.
[8] S. M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proceedings-Mathematical Sciences, 130(1) (2020), 1–15.
[9] S. M. Mirafzal, Cayley properties of the line graphs induced by consecutive layers of the hypercube, Bull. Malays. Math. Sci. Soc., 44(3) (2021), 1309–1326.
[10] S. M. Mirafzal, The line graph of the crown graph is distance integral, Linear and Multilinear Algebra, https://doi.org/10.1080/03081087.2022.2040941, 2022.
[11] S. M. Mirafzal, On the distance eigenvalues of design graphs, arXiv preprint, arXiv:2111.05239v4, 2022.
[12] M. Pokorny, P. Hic, D. Stevanovic and M. Milosevic, On distance integral graphs, Discrete Math., 338 (2015), 1784–1792.