Some new classes of distance integral graphs constructed from integral graphs
Subject Areas : Combinatorics, Graph theory
1 - Department of Mathematics, Lorestan University, Khoramabad, Iran
Keywords: Distance integral, vertex-transitive, distance regular, bipartite Kneser graph,
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. In this paper, we introduce some new classes of distance integral graphs. In particular, we show that if $n,k$ are integers such that $n \geq 3k >0$, then the bipartite Kneser graph $H(n,k)$ is distance integral. Moreover, we determine the distance spectrum of $H(n,k)$. Also, we show that every distance regular integral graph is distance integral.
[1] M. Aouchiche, P. Hansen, Distance spectra of graphs: a survey, Linear Algebra. Appl. 458 (2014), 301-386.
[2] K. Baliaska, D. Cvetkovic, Z Radosavljevic, S. Simic, D. Stevanovic, A survey on integral graphs, Publ. Elektroteh. Fak. Univ. Beogr. Ser. Mat. 13 (2002), 42-65.
[3] N. L. Biggs, Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, 1993.
[4] A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag, New York, 1989.
[5] C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001.
[6] F. Harary, A. J. Schwenk, Which Graphs Have Integral Spectra? In Graphs and Combinatorics, Lecture Notes in Mathematics, Springer-Verlag, 406, 1974.
[7] E. V. Konstantinova, D. Lytkina, Integral Cayley graphs over finite groups, Algebra Colloquium. 27 (1) (2020), 131-136.
[8] H. Lin, J. Shu, J. Xue, Y. Zhang, A survey on distance spectra of graphs, Adv. Math. 50 (1) (2021), 29-76.
[9] Y. Lin, W. Yan, Z. Ouyang, On the p-restricted edge connectivity of the bipartite Kneser graph H(n,k), Australasian. J. Combinatorics. 83 (2) (2022), 265-73.
[10] T. Matsushita, Graphs whose Kronecker covers are bipartite Kneser graphs, Discrete Math. 344 (2021), 4:112264.
[11] S. M. Mirafzal, A new class of integral graphs constructed from the hypercube, Linear Algebra. Appl. 558 (2018), 186-194.
[12] S. M. Mirafzal, Cayley properties of the line graphs induced by consecutive layers of the hypercube, Bull. Malaysian Math. Sci. 44 (2021), 1309-1326.
[13] S. M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proc. Math. Sci. 130 (2020), 130:57.
[14] S. M. Mirafzal, Some remarks on the square graph of the hypercube, Ars Mathematica Contemporanea. 23 (2023), 2:06.
[15] S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Math. Sci. 129 (2019), 129:34.
[16] S. M. Mirafzal, The line graph of the crown graph is distance integral, Linear and Multilinear Algebra. (2022), in press.
[17] S. M. Mirafzal, R. Kogani, On determining the distance spectrum of a class of distance integral graphs, J. Algebra Syst. 10 (2) (2023), 299-308.
[18] S. M. Mirafzal, A. Zafari, On the spectrum of a class of distance-transitive graphs, Electronic J. Graph Theory. Appl. 5 (1) (2017), 63-69.
[19] M. Pokorny, P. Hic, D. Stevanovic, M. Milosevic, On distance integral graphs, Discrete Math. 338 (2015), 1784-1792.
[20] P. Reinfeld, Chromatic polynomials and the spectrum of the Kneser graphs, Preprint, 2000.
[21] J. J. Rotman, Advanced Modern Algebra, American Mathematical Society, 165, 2015.