The distance spectrum of two new operations of graphs

Document Type : Research Paper


Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), College of Mathematics and Sta- tistics, Hunan Normal University, Changsha, Hunan 410081, P. R. China


Let $G$ be a connected graph with vertex set $V(G)=\{v_1, v_2,\ldots,v_n\}$‎. ‎The distance matrix $D=D(G)$ of $G$ is defined so that its $(i,j)$-entry is equal to the distance $d_G(v_i,v_j)$ between the vertices $v_i$ and $v_j$ of $G$‎. ‎The eigenvalues ${\mu_1, \mu_2,\ldots,\mu_n}$ of $D(G)$ are the $D$-eigenvalues of $G$ and form the distance spectrum or the $D$-spectrum of $G$‎, ‎denoted by $Spec_D(G)$‎. ‎In this paper‎, ‎we introduce two new operations $G_1\blacksquare_k G_2$ and $G_1\blacklozenge_k G_2$ on graphs $G_1$ and $G_2$‎, ‎and describe the distance spectra of $G_1\blacksquare_k G_2$ and $G_1\blacklozenge_k G_2$ of regular graphs $G_1$ and $G_2 $ in terms of their adjacency spectra‎. ‎By using these results‎, ‎we obtain some new integral adjacency spectrum graphs‎, ‎integral distance spectrum graphs and a number of families of sets of noncospectral graphs with equal distance energy‎.


Main Subjects

[1] M. Aouchiche and P. Hansen, Distance spectra of graphs: A survey, Lin. Algebra Appl., 458 (2014) 301–386.
[2] K. Balasubramanian, Computer generation of distance polynomials of graphs, Journal of Computational Chemistry,
11 (1990) 829–836.
[3] K. Balińska, D. Cvetković, M. Lepović and S. Simić, There are exactly 150 connected integral graphs up to 10
vertices, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat., 10 (1999) 95–105.
[4] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs–Theory and Application, third ed., Johann Ambrosius
Barth Verlag, 1995.
[5] H. Deng, S. Balachandran, S. K. Ayyaswamy and Y. B. Venkatakrishnan, On the average eccentricity, the harmonic
index and the largest signless Laplacian eigenvalue of a graph, 6 (2017) 43–50.
[6] R. L. Graham and L. Lovasz, Distance matrix polynomials of trees, Adv. Math., 29 (1978) 60–88.
[7] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J., 50 (1971)
[8] A. Heydari, On the spectra of reduced distance matrix of dendrimers, 2 (2013) 41–46.
[9] G. Indulal and R. Balakrishnan, Distance spectrum of Indu-Bala product of graphs, AKCE International Journal
of Graphs and Combinatorics, (2016) 230–234.
[10] G. Indulal, I. Gutman and A. Vijayakumar, On distance energy of graphs, MATCH Commun. Math. Comput.
Chem., 60 (2008) 461–472.
[11] D. Stevanović a G. Indulal, The distance spectrum and energy of the compositions of regular graphs, Appl. Math.
Lett., 22 (2009) 1136–1140.
[12] Z. Stanić, There are exactly 172 connected Q-integral graphs up to 10 vertices, Novi. Sad. J. Math., 37 (2001)
Volume 9, Issue 3 - Serial Number 3
September 2020
Pages 125-138
  • Receive Date: 09 April 2019
  • Revise Date: 06 February 2020
  • Accept Date: 13 February 2020
  • Published Online: 01 September 2020