Spectral determination of trees with large diameter and small spectral radius

Document Type : Original paper

Authors

1 School of Mathematics and Statistics, Shandong University of Technology, Zibo 255049, China

2 Haide School, Ocean University of China, Qingdao 266100, China

3 Department of Mathematics and Applications, University of Naples Federico II, Naples, Italy

Abstract

Yuan, Shao and Liu proved  that the H-shape tree $H'_n =P_{1,2;n-3}^{1,n-6}$ minimizes the spectral radius among all graphs with order $n\geqslant 9$ and diameter $n-4$. In this paper, we achieve the spectral characterization of all graphs in the set $\mathscr{H}' = \{ H'_n\}_{n\geqslant 8}$. More precisely we show that $H'_n$ is determined by its spectrum if and only if $n \neq 8, 9,12$, and detect all cospectral mates of $H'_8$, $H'_9$ and $H'_{12}$. Divisibility between characteristic polynomials of graphs turns out to be an important tool to reach our goals.

Keywords

Main Subjects

References

[1] A.E. Brouwer and A. Neumaier, The graphs with spectral radius between 2 and $\sqrt{2+\sqrt{5}}$, Linear Algebra Appl. 114 (1989), 273–276.   https://doi.org/10.1016/0024-3795(89)90466-7
[2] Z. Chen, J. Wang, M. Brunetti, and F. Belardo, On the divisibility of H-shape trees and their spectral determination, Linear Algebra Appl. 675 (2023), 312–337.  https://doi.org/10.1016/j.laa.2023.06.028
[3] S.M. Cioabă, E.R. van Dam, J.H. Koolen, and J.H. Lee, Asymptotic results on the spectral radius and the diameter of graphs, Linear Algebra Appl. 432 (2010), no. 2–3, 722–737.  https://doi.org/10.1016/j.laa.2009.09.016
[4] D. Cvetković, M. Doob, and I. Gutman, On graphs whose spectral radius does not exceed $\sqrt{2+\sqrt{5}}$, Ars Combin. 14 (1982), 225–239.
[5] D.M. Cvetković, M. Doob, and H. Sachs, Spectral of Graphs Theory and Applications, Academic Press, New York, San Francisco, London, 1980.
[6] E.J. Farrell, J.M. Guo, and G.M. Constantine, On matching coefficients, Discrete Math. 89 (1991), no. 2, 203–210. https://doi.org/10.1016/0012-365X(91)90369-D
[7] N. Ghareghani, G.R. Omidi, and B. Tayfeh-Rezaie, Spectral characterization of graphs with index at most  $\sqrt{2+\sqrt{5}}$, Linear Algebra Appl. 420 (2007), no. 2–3, 483–489.  https://doi.org/10.1016/j.laa.2006.08.009
[8] N. Ghareghani, F. Ramezani, and B. Tayfeh-Rezaie, Graphs cospectral with starlike trees, Linear Algebra Appl. 429 (2008), no. 11-12, 2691–2701.  https://doi.org/10.1016/j.laa.2008.01.001
[9] A.J. Hoffman and J.H. Smith, On the spectral radii of topologically equivalent graphs, Recent Advances in Graph Theory (M. Fiedler, ed.), Academia Praha, 1975, pp. 273–281.  
[10] S. Hu, On the spectral characterization of H-shape trees, Adv. Linear Algebra & Matrix Theory 4 (2014), no. 2, 79–86.  http://dx.doi.org/10.4236/alamt.2014.42005
[11] J. Lan and L. Lu, Diameters of graphs with spectral radius at most $\frac{3}{2}\sqrt{2}$, Linear Algebra Appl. 438 (2013), no. 11, 4382–4407.  https://doi.org/10.1016/j.laa.2012.12.047
[12] J. Lan, L. Lu, and L. Shi, Graphs with diameter $n − e$ minimizing the spectral radius, Linear Algebra Appl. 437 (2012), no. 11, 2823–2850.   https://doi.org/10.1016/j.laa.2012.05.038
[13] J. Lan and L. Shi, Graphs of order n and diameter $\frac{2(n − 1)}{3}$ minimizing the spectral radius, Linear Algebra Appl. 486 (2015), 219–233.  https://doi.org/10.1016/j.laa.2015.08.015
[14] M. Lepović and I. Gutman, No starlike trees are cospectral, Discrete Math. 242 (2002), no. 1-3, 291–295. https://doi.org/10.1016/S0012-365X(01)00169-8
[15] F. Liu and Q. Huang, On the spectral characterization of π-shape trees, Linear Multilinear Algebra 61 (2013), no. 3, 355–367.  https://doi.org/10.1080/03081087.2012.672569
[16] F. Liu, Q. Huang, and Q. Liu, Spectral characterization of †-shape trees, Electron. J. Linear Algebra 22 (2011), 822–837.  https://doi.org/10.13001/ela.2011.955
[17] A.J. Schwenk, Almost all trees are cospectral, New Directions in the Theory of Graphs (F. Harary, ed.), Academic Press, New York, 1973, pp. 275–307. 
[18] A.J. Schwenk, Computing the characteristic polynomial of a graph, Graphs and Combinatorics, Lect. Notes in Math. 406, 1973, pp. 275–307.
[19] X.L. Shen, Y.P. Hou, and Y.P. Zhang, Graph zn and some graphs related to $Z_n$ are determined by their speetrum, Linear Algebra Appl. 404 (2005), 58–68.  https://doi.org/10.1016/j.laa.2005.01.036
[20] J.H. Smith, Some properties of the spectrum of a graph, Combinatorial Structures and their applications (1970), 403–406.
[21] E.R. van Dam and W.H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241–272.   https://doi.org/10.1016/S0024-3795(03)00483-X
[22] E.R. Van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009), no. 3, 576–586.   https://doi.org/10.1016/j.disc.2008.08.019
[23] E.R. van Dam and R.E. Kooij, The minimal spectral radius of graphs with a given diameter, Linear Algebra Appl. 423 (2007), no. 2–3, 408–419.  https://doi.org/10.1016/j.laa.2007.01.011
[24] W. Wang and C.X. Xu, On the spectral characterization of $t$-shape trees, Linear Algebra Appl. 414 (2006), no. 2-3, 492–501.  https://doi.org/10.1016/j.laa.2005.10.031
[25] R. Woo and A. Neumaier, On graphs whose spectral radius is bounded by $\frac{3}{2}\sqrt{2}$,Graphs Combin. 23 (2007), no. 6, 713–726.  https://doi.org/10.1007/s00373-007-0745-9
[26] X.Y. Yuan, J.Y. Shao, and Y. Liu, The minimal spectral radius of graphs of order n with diameter $n-4$, Linear Algebra Appl 428 (2008), no. 11-12, 2840–2851.  https://doi.org/10.1016/j.laa.2008.01.011
Communications in Combinatorics and Optimization
Volume 9, Issue 4
December 2024
Pages 607-623

Files

Share

How to cite

Statistics