Cacti Whose Spread is Maximal
Tóm tắt
For a simple graph G, the graph’s spread s(G) is defined as the difference between the largest eigenvalue and the least eigenvalue of the graph’s adjacency matrix, i.e.
$${s(G)=\rho(G)-\lambda(G)}$$
. A connected graph G is a cactus if any two of its cycles have at most one common vertex. If all cycles of the cactus G have exactly one common vertex then it is called a bundle. Let
$${{\mathcal C}(n,k)}$$
denote the class of cacti with n vertices and k cycles. In this paper, we determine a unique cactus whose spread is maximal among the cacti with n vertices and k cycles. We prove that the obtained graph is a bundle of a special form. Within the class
$${{\mathcal C}(n,k)}$$
we also present a unique cactus whose least eigenvalue is minimal (Petrović et al. in Linear Algebra Appl 435:2357–2364, 2011) and show that these two graphs are the same, except for a few cases in which n is small.
Tài liệu tham khảo
Borovićanin B., Petrović M.: On the index of cactuses with n vertices. Publications de l’Institut Mathématique 79(93), 13–18 (2006)
Cvetković, D., Doob, M., Sachs, H.: Spectra of Graphs: Theory and Applications, 3rd edn. Johann Ambrosius Barth, Heidelberg (1995)
Cvetković, D.; Rowlinson, P.; Simić, S.K.: Eigenspaces of Graphs. Cambridge University Press, Cambridge (1997)
Fan Y.Z., Wang Y., Gao Y.B.: Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread. Linear Algebra Appl. 429, 577–588 (2008)
Gregory D.A., Hershkowith D., Kirkland S.J.: The spread of the spectrum of a graph. Linear Algebra Appl. 332, 23–35 (2001)
Hoffman, A.J.; Smith, J.H.: On the spectral radii of topologically equivalent graphs. In: Fiedler, M. (ed.) Recent Advances in Graph Theory, pp. 273–281. Academia Praha, New York (1975)
Petrović M.: On graphs whose spectral spread does not exceed 4. Publications de l’Institut Mathématique 34(48), 169–174 (1983)
Petrović M., Aleksić T., Simić S.K.: Further results on the least eigenvalue of connected graphs. Linear Algebra Appl. 435, 2303–2313 (2011)
Petrović M., Aleksić T., Simić V.: On the least eigenvalue of cacti. Linear Algebra Appl. 435, 2357–2364 (2011)
Petrović M., Borovićanin B., Aleksić T.: Bicyclic graphs for which the least eigenvalue is minimal. Linear Algebra Appl. 430, 1328–1335 (2009)
Radosavljević Z., Rašajski M.: A class of reflexive cacti with four cycles. Publ. Fac. Electr. Eng. Ser. Math. 14, 64–85 (2003)
Wu B., Xiao E., Hong Y.: The spectral radius of trees on k pendant vertices. Linear Algebra Appl. 395, 343–349 (2005)