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 Hn′=P1,2;n−31,n−6 minimizes the spectral radius among all graphs with order n⩾9 and diameter n−4. In this paper, we achieve the spectral characterization of all graphs in the set H′={Hn′}n⩾8. More precisely we show that Hn′ is determined by its spectrum if and only if n≠8,9,12, and detect all cospectral mates of H8′, H9′ and H12′. 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 2+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 2+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  2+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 322, 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 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 Zn 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 322,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