Sharp upper bounds of $A_\alpha$-spectral radius of cacti with given pendant vertices

Abstract

For $ \alpha \in [0,1]$, let $A_{\alpha}(G) = \alpha D(G) +(1-\alpha)A(G)$ be $A_{\alpha}$-matrix, where $A(G)$ is the adjacent matrix and $D(G)$ is the diagonal matrix of the degrees of a graph $G$. Clearly, $A_{0} (G)$ is the adjacent matrix and $2 A_{\frac{1}{2}}$ is the signless Laplacian matrix. A connected graph is a cactus graph if any two cycles of $G$ have at most one common vertex. We first propose the result for subdivision graphs, and determine the cacti maximizing $A_{\alpha}$-spectral radius subject to fixed pendant vertices. In addition, the corresponding extremal graphs are provided. As consequences, we determine the graph with the $A_{\alpha}$-spectral radius among all the cacti with $n$ vertices; we also characterize the $n$-vertex cacti with a perfect matching having the largest $A_{\alpha}$-spectral radius.

Keywords

• Adjacent matrix
• trees
• cacti
• bounds

References

1. [1] A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM: Philadelphia, PA, USA, 1994.
2. [2] B. Bollobás, Modern Graph Theory, Springer: New York, NY, USA, 1998.
3. [3] B. Borovićanin and M. Petrović, On the index of cactuses with n vertices, Publ. Inst. Math 79 (93), 13-18, 2006.
4. [4] Y. Chen, Properties of spectra of graphs and line graphs, Appl. Math. J. Chinese Univ. Ser. B 17 (3), 371-376, 2002.
5. [5] M. Chen and B. Zhou, On the Signless Laplacian Spectral Radius of Cacti, Croat. Chem. Acta 89 (4), 493-498, 2016.
6. [6] L. Collatz and U. Sinogowitz, Spektrcn endlicher Graten, Abh. Math. Scm. Univ. Hamburg 21, 63-77, 1957.
7. [7] L. Cui, Y.-Z. Fan, The signless laplacian spectral radius of graphs with given number of cut vertices, Discuss. Math. Graph Theory 30 (1), 85-93, 2010.
8. [8] D. Cvetković, P. Rowlinson and SK. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (3), 155-171, 2007.

9. [9] D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2009.
10. [10] L. Feng , Q. Li and X.-D. Zhang, Minimizing the Laplacian spectral radius of trees with given matching number, Linear Multilinear Algebra 55, 199-207, 2007.
11. [11] J. Huang and S. Li, On the Spectral Characterizations of Graphs, Discuss. Math. Graph Theory 37, 729-744, 2017.
12. [12] S. Li and M. Zhang, On the signless Laplacian index of cacti with a given number of pendant vertices, Linear Algebra Appl. 436, 4400-4411, 2012.
13. [13] H. Lin and B. Zhou, Graphs with at most one signless Laplacian eigenvalue exceeding three, Linear Multilinear Algebra 63 (3), 377-383, 2015.
14. [14] L. Lovász and J. Pelikán, On the eigenvalues of trees, Period. Math. Hungar 3, 175- 182, 1973.
15. [15] V. Nikiforov, Merging the A- and Q-spectral theories, Appl. Anal. Discrete Math. 11, 81-107, 2017.
16. [16] V. Nikiforov, G. Pastén, O. Rojo and R.L. Soto, On the $A_{\alpha}$-spectra of trees, Linear Algebra Appl. 520 (3), 286-305, 2017.
17. [17] Y. Shen, L. You, M. Zhang and S. Li, On a conjecture for the signless Laplacian spectral radius of cacti with given matching number, Linear Multilinear Algebra 65 (4), 457-474, 2017.
18. [18] J. Wu, H. Deng and Q. Jiang, On the spectral radius of cacti with k-pendant vertices, Linear Multilinear Algebra 58, 391-398, 2010.
19. [19] T. Wu and H. Zhang, Per-spectral characterizations of some bipartite graphs, Discuss. Math. Graph Theory 37, 935-951, 2017.
20. [20] R. Xing and B. Zhou, On the least eigenvalue of cacti with pendant vertices, Linear Algebra Appl. 438, 2256-2273, 2013.
21. [21] J. Xue, H. Lin, S. Liu and J. Shu, On the $A_{\alpha}$-spectral radius of a graph, Linear Algebra Appl. 550, 105-120, 2018.
22. [22] Y. Yan, C.Wang and S.Wang, The $A_{\alpha}$-spectral radii of trees with specified maximum degree, submitted.
23. [23] A. Yu, M. Lu and F. Tian, On the spectral radius of graphs, Linear Algebra Appl. 387, 41-49, 2004.
24. [24] Bo. Zhou, Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl 423 (3), 566-570, 2010.