Cacti with a Given Spectral Property

Authors: M. Petrović, Z. Radosavljević, M. Rašajski

Keywords: Graph, cactus, index, least eigenvalue, spread, reflexive graphs.

Abstract:

A connected graph G is a cactus if any two of its cycles have at most one common vertex. This article is a survey of results concerning cacti with a given spectral property, categorized as follows: (1) extremal cacti, (2) reflexive cacti.

References:

[1] B. BOROVIćANIN, M. PETROVIć , On the index of cactuses with n vertices, Publ. Inst. Math. (Beograd) 79 (93) (2006), 13-18. [2] A. CHANG, On the largest eigenvalue of a tree with perfect matching, Discrete Math., 269 (2003), 45-63. [3] A. CHANG, F. TIAN, On the spectral radius on unicyclic graphs with perfect matching, Linear Algebra Appl., 370 (2003), 237-250. [4] L. COLLATZ, U. SINOGOWITZ, Spektren endlicher Grafen, Abh.Math. Sem. Univ. Hamburg 21(1957), 63-77. [5] D. CVETKOVIć , M. DOOB, I. GUTMAN, A. TORGAšEV, Recent Results in the Theory of Graph Spectra, North-Holland (Amsterdam), 1988. [6] D. CVETKOVIć, M. DOOB, H. SACHS, Spectra of graphs – Theory and Applications, Deutscher Verlag der Wissenschaften, Academic Press, Berlin, New York, 1980 (third ed., Johann Ambrosius Barth, Heidelberg, Leipzig, 1995). [7] D. CVETKOVIć, M. PETRIć, A table of connected graphs on six vertices, Discrete Math. 50(1984), 37-49. [8] Z. HUANG, H, DENG, S. SIMIć, On the spectral radius of cactuses with perfect matchings, Appl. Anal. Discrete Math. 5(2011), 14-21. [9] T. KOLEDIN, Z. RADOSAVLJEVIć, Unicyclic reflexive graphs with seven loaded vertices of the cycle, Filomat 23:3 (2009), pp. 253-264. [10] L. LOVASZ, J. PELIKAN, On the eigenvalues of trees, Periodica Math. Hung. 3(1973), 175- 182. [11] G. MAXWELL, Hypebolic trees, J. Algebra 54 (1978), 46-49. [12] B. MIHAILOVIć , Z. RADOSAVLJEVIć , On a class of tricyclic reflexive cactuses, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 16 (2005), 55-63. [13] A. NEUMAIER, The second largest eigenvalue of a tree, Linear Algebra and its Appl., 46 (1982), 9–25. [14] A. NEUMAIER, J. J. SEIDEL, Discrete hyperbolic geometry, Combinatorica, 3 (2) (1983), 219-237. [15] M. PETROVIć, T. ALEKSIć, V. SIMIć, On the least eigenvalue of cacti, Linear Algebra Appl. (2011), doi:10.1016/j.laa.2011.02.011. [16] M. PETROVIć , Z. RADOSAVLJEVIć, Spectrally constrained graphs, Fac. of Science, Kragujevac, Serbia, 2001. [17] Z. RADOSAVLJEVIć, On unicyclic reflexive graphs, Applicable Analysis and Discrete Mathematics 1 (2007), pp. 228-240. [18] Z. RADOSAVLJEVIć, B. MIHAILOVIć, M. RAšAJSKI, Decomposition of Smith graphs in maximal reflexive cacti, Discrete Mathematics, Volume 308, Issues 2-3, 6 Feb 2008, 355-366. [19] Z. RADOSAVLJEVIć, B. MIHAILOVIć , M. RAšAJSKI, On bicyclic reflexive graphs, Discrete Mathematics, Volume 308, Issues 5-6, 28 March 2008, Pages 715-725. [20] Z. RADOSAVLJEVIć , M. RAšAJSKI, A class of reflexive cacti with four cycles, Univ. Beograd, Publ.Elektrotehn.Fak., Ser.Mat., 14 (2003), 64–85. [21] Z. RADOSAVLJEVIć , M. RAšAJSKI, Multicyclic treelike reflexive graphs, Discrete Math., Vol. 296/1 (2005), 43-57. [22] Z. RADOSAVLJEVIć , S. SIMIć, Which bicyclic graphs are reflexive?, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 7 (1996), 90-104. [23] M. RAšAJSKI, Višekonturni refleksivni grafovi, PhD thesis,Mat. Fak. Univ. u Beogradu, 2006. [24] A. SCHWENK, Computing the charateristic polynomial of a graph, in:R. Bari, F. Harary (Eds.), Graphs and Combinatorics – Lecture Notes in Mathematics, vol. 406, Springer-Verlag, Berlin, Heidelrberg, New York, 1974, 153-172. [25] J. H. SMITH, Some properties of the spectrum of a graph, In: Combinatorial Structures and Their Applications. Ed. R. Guy, H. Hanani, N. Sauer, J. Schonheim. Gordon and Breach, Science Publ., Inc., New York–London–Paris 1970, 403–406. [26] D. STEVANOVIć , V. BRANKOV, D. CVETKOVIć, S. SIMIć , newGRAPH, the expert system, http://www.mi.sanu.ac.rs/newgraph. [27] G. XU, On the spectral radius of trees with perfect matchings, Combinatoris and Graph theory, World Scientific, Singapure, 1997