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
[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.