آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 108 |
| تعداد مقالات | 1,228 |
| تعداد مشاهده مقاله | 1,146,445 |
| تعداد دریافت فایل اصل مقاله | 1,004,996 |
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 Gao1؛ Xuanshi Jia2؛ JianFeng Wang1؛ Maurizio Brunetti* 3 | ||
| 1School of Mathematics and Statistics, Shandong University of Technology, Zibo 255049, China | ||
| 2Haide School, Ocean University of China, Qingdao 266100, China | ||
| 3Department 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 | ||
|
آمار تعداد مشاهده مقاله: 343 تعداد دریافت فایل اصل مقاله: 1,032 |
||