Spectral determination of trees with large diameter and small spectral radius

Gao, Xing; Jia, Xuanshi; Wang, Jianfeng; Brunetti, Maurizio

doi:10.22049/cco.2023.28648.1651

تعداد نشریات	6
تعداد شماره‌ها	125
تعداد مقالات	1,584
تعداد مشاهده مقاله	1,747,273
تعداد دریافت فایل اصل مقاله	1,624,445

	Spectral determination of trees with large diameter and small spectral radius
Communications in Combinatorics and Optimization
مقاله 1، دوره 9، شماره 4، اسفند 2024، صفحه 607-623 اصل مقاله (529.25 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28648.1651
نویسندگان
Xing Gao¹؛ Xuanshi Jia²؛ Jianfeng Wang¹؛ Maurizio Brunetti^* ³
¹School of Mathematics and Statistics, Shandong University of Technology, Zibo 255049, China
²Haide School, Ocean University of China, Qingdao 266100, China
³Department of Mathematics and Applications, University of Naples Federico II, Naples, Italy
چکیده
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.
کلیدواژه‌ها
Adjacency spectrum؛ Spectral characterization؛ DS-graph؛ Matchings؛ Spectral radius

مراجع
[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
آمار تعداد مشاهده مقاله: 764 تعداد دریافت فایل اصل مقاله: 2,073

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Spectral determination of trees with large diameter and small spectral radius