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‎, ‎k\geq1$‎. ‎The bipartite Kneser graph $H(n,k)$ is the graph with the set of all $k$ and $n-k$ 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.