Some new classes of distance integral graphs constructed from integral graphs

Subject Areas : Combinatorics, Graph theory

S. M. Mirafzal ¹

1 - Department of Mathematics, Lorestan University, Khoramabad, Iran

Received: 2023-02-27 Accepted : 2023-03-28 Published : 2023-03-30

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

References:

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