# Institute of Mathematics

## Graphs with small diameter determined by their $D$-spectra

#### Ruifang Liu, Jie Xue

###### Received September 22, 2015.   First published January 10, 2018.

Abstract:  Let $G$ be a connected graph with vertex set $V(G)=\{v_1,v_2,\ldots,v_n\}$. The distance matrix $D(G)=(d_{ij})_{n\times n}$ is the matrix indexed by the vertices of\/ $G$, where $d_{ij}$ denotes the distance between the vertices $v_i$ and $v_j$. Suppose that $\lambda_1(D)\geq\lambda_2(D)\geq\cdots\geq\lambda_n(D)$ are the distance spectrum of $G$. The graph $G$ is said to be determined by its $D$-spectrum if with respect to the distance matrix $D(G)$, any graph having the same spectrum as $G$ is isomorphic to $G$. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their $D$-spectra.
Keywords:  distance spectrum; distance characteristic polynomial; $D$-spectrum determined by its $D$-spectrum
Classification MSC:  05C50
DOI:  10.21136/CMJ.2018.0505-15

PDF available at:  Springer   Myris Trade   Institute of Mathematics CAS

References:
[1] S. M. Cioabă, W. H. Haemers, J. R. Vermette, W. Wong: The graphs with all but two eigenvalues equal to $\pm 1$. J. Algebra Comb. 41 (2015), 887-897. DOI 10.1007/s10801-014-0557-y | MR 3328184 | Zbl 1317.05111
[2] D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs. Theory and Applications. J. A. Barth Verlag, Heidelberg (1995). DOI 10.1002/zamm.19960760305 | MR 1324340 | Zbl 0824.05046
[3] H. H. Günthard, H. Primas: Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit systemen konjugierter Bindungen. Helv. Chim. Acta 39 (1956), 1645-1653. (In German.) DOI 10.1002/hlca.19560390623
[4] Y.-L. Jin, X.-D. Zhang: Complete multipartite graphs are determined by their distance spectra. Linear Algebra Appl. 448 (2014), 285-291. DOI 10.1016/j.laa.2014.01.029 | MR 3182986 | Zbl 1285.05114
[5] L. Lu, Q. X. Huang, X. Y. Huang: The graphs with exactly two distance eigenvalues different from $-1$ and $-3$. J. Algebr. Comb. 45 (2017), 629-647. DOI 10.1007/s10801-016-0718-2 | MR 3604069 | Zbl 1358.05176
[6] H. Q. Lin: On the least distance eigenvalue and its applications on the distance spread. Discrete Math. 338 (2015), 868-874. DOI 10.1016/j.disc.2015.01.00610.1016/j.disc.2015.01.006 | MR 3318625 | Zbl 1371.05064
[7] H. Q. Lin, Y. Hong, J. F. Wang, J. L. Shu: On the distance spectrum of graphs. Linear Algebra Appl. 439 (2013), 1662-1669. DOI 10.1016/j.laa.2013.04.019 | MR 3073894 | Zbl 1282.05132
[8] H. Q. Lin, M. Q. Zhai, S. C. Gong: On graphs with at least three distance eigenvalues less than $-1$. Linear Algebra Appl. 458 (2014), 548-558. DOI 10.1016/j.laa.2014.06.040 | MR 3231834 | Zbl 1296.05123
[9] R. F. Liu, J. Xue, L. T. Guo: On the second largest distance eigenvalue of a graph. Linear Multilinear Algebra 65 (2017), 1011-1021. DOI 1080/03081087.2016.1221376 | MR 3610302 | Zbl 1360.05099
[10] E. R. van Dam, W. H. Haemers: Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003), 241-272. DOI 10.1016/S0024-3795(03)00483-X | MR 2022290 | Zbl 1026.05079
[11] E. R. van Dam, W. H. Haemers: Developments on spectral characterizations of graphs. Discrete Math. 309 (2009), 576-586. DOI 10.1016/j.disc.2008.08.019 | MR 2499010 | Zbl 1205.05156
[12] J. Xue, R. F. Liu, H. C. Jia: On the distance spectrum of trees. Filomat 30 (2016), 1559-1565. DOI 10.2298/FIL1606559X | MR 3530101 | Zbl 06749814

Affiliations:   Ruifang Liu (corresponding author), Jie Xue, School of Mathematics and Statistics, Zhengzhou University, 100 Ke Xue Road, Zhengzhou 450001, Henan, China, e-mail: rfliu@zzu.edu.cn

Springer subscribers can access the papers on Springer website.