Cacti Whose Spread is Maximal

Springer Science and Business Media LLC - Tập 31 - Trang 23-34 - 2013
Tatjana M. Aleksić1, Miroslav Petrović2
1Faculty of Science, University of Kragujevac, Kragujevac, Serbia
2State University of Novi Pazar, Novi Pazar, Serbia

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)