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