Czechoslovak Mathematical Journal, first online, pp. 1-17


Unbalanced unicyclic and bicyclic graphs with extremal spectral radius

Francesco Belardo, Maurizio Brunetti, Adriana Ciampella

Received September 13, 2019.   Published online September 23, 2020.

Abstract:  A signed graph $\Gamma$ is a graph whose edges are labeled by signs. If $\Gamma$ has $n$ vertices, its spectral radius is the number $\rho(\Gamma) := \max\{ | \lambda_i(\Gamma) | \colon1 \leq i \leq n \}$, where $\lambda_1(\Gamma) \geq\cdots\geq\lambda_n(\Gamma)$ are the eigenvalues of the signed adjacency matrix $A(\Gamma)$. Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes $\frak U_n$ and $\frak B_n$ of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.
Keywords:  signed graph; spectral radius; bicyclic graph
Classification MSC:  05C50, 05C22
DOI:  10.21136/CMJ.2020.0403-19

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] S. Akbari, F. Belardo, E. Dodongeh, M. A. Nematollahi: Spectral characterizations of signed cycles. Linear Algebra Appl. 553 (2018), 307-327. DOI 10.1016/j.laa.2018.05.012 | MR 3809382 | Zbl 1391.05126
[2] S. Akbari, F. Belardo, F. Heydari, M. Maghasedi, M. Souri: On the largest eigenvalue of signed unicyclic graphs. Linear Algebra Appl. 581 (2019), 145-162. DOI 10.1016/j.laa.2019.06.016 | MR 3982012 | Zbl 1420.05070
[3] S. Akbari, W. H. Haemers, H. R. Maimani, L. Parsaei Majd: Signed graphs cospectral with the path. Linear Algebra Appl. 553 (2018), 104-116. DOI 10.1016/j.laa.2018.04.021 | MR 3809370 | Zbl 1391.05156
[4] F. Belardo, M. Brunetti: Connected signed graphs $L$-cospectral to signed $\infty$-graphs. Linear Multilinear Algebra 67 (2019), 2410-2426. DOI 10.1080/03081087.2018.1494122 | MR 4017722 | Zbl 1425.05067
[5] F. Belardo, M. Brunetti, A. Ciampella: Signed bicyclic graphs minimizing the least Laplacian eigenvalue. Linear Algebra Appl. 557 (2018), 201-233. DOI 10.1016/j.laa.2018.07.026 | MR 3848268 | Zbl 1396.05066
[6] F. Belardo, S. Cioabă, J. Koolen, J. Wang: Open problems in the spectral theory of signed graphs. Art Discrete Appl. Math. 1 (2018), Article ID P2.10, 23 pages. DOI 10.26493/2590-9770.1286.d7b | MR 3997096 | Zbl 1421.05052
[7] F. Belardo, E. M. Li Marzi, S. K. Simić: Some results on the index of unicyclic graphs. Linear Algebra Appl. 416 (2006), 1048-1059. DOI 10.1016/j.laa.2006.01.008 | MR 2242480 | Zbl 1092.05043
[8] R. A. Brualdi, E. S. Solheid: On the spectral radius of connected graphs. Publ. Inst. Math., Nouv. Sér. 39 (1986), 45-54. MR 0869175 | Zbl 0603.05028
[9] M. Brunetti: On the existence of non-golden signed graphs. Atti Accad. Peloritana Pericolanti, Cl. Sci. Fis. Mat. Nat. 96 (2018), Article A2, 10 pages. DOI 10.1478/AAPP.96S2A2 | MR 3900933
[10] A. Chang, F. Tian, A. Yu: On the index of bicyclic graphs with perfect matchings. Discrete Math. 283 (2004), 51-59. DOI 10.1016/j.disc.2004.02.005 | MR 2060353 | Zbl 1064.05118
[11] D. Cvetković, P. Rowlinson: Spectra of unicyclic graphs. Graphs Comb. 3 (1987), 7-23. DOI 10.1007/BF01788525 | MR 0932109 | Zbl 0623.05038
[12] D. Cvetković, P. Rowlinson, S. Simić: Eigenspaces of Graphs. Encyclopedia of Mathematics and Its Applications 66. Cambridge University Press, Cambridge (1997). DOI 10.1017/CBO9781139086547 | MR 1440854 | Zbl 0878.05057
[13] S.-G. Guo: The spectral radius of unicyclic and bicyclic graphs with $n$ vertices and $k$ pendant vertices. Linear Algebra Appl. 408 (2005), 78-85. DOI 10.1016/j.laa.2005.05.022 | MR 2166856 | Zbl 1073.05550
[14] S.-G. Guo: On the spectral radius of bicyclic graphs with $n$ vertices and diameter $d$. Linear Algebra Appl. 422 (2007), 119-132. DOI 10.1016/j.laa.2006.09.011 | MR 2298999 | Zbl 1112.05064
[15] J. McKee, C. Smyth: Integer symmetric matrices having all their eigenvalues in the interval $[-2, 2]$. J. Algebra 317 (2007), 260-290. DOI 10.1016/j.jalgebra.2007.05.019 | MR 2360149 | Zbl 1140.15007
[16] S. K. Simić: On the largest eigenvalue of unicyclic graphs. Publ. Inst. Math., Nouv. Sér. 42 (1987), 13-19. MR 0937447 | Zbl 0641.05040
[17] S. K. Simić: On the largest eigenvalue of bicyclic graphs. Publ. Inst. Math., Nouv. Sér. 46 (1989), 1-6. MR 1060049 | Zbl 0747.05058
[18] Z. Stanić: Bounding the largest eigenvalue of signed graphs. Linear Algebra Appl. 573 (2019), 80-89. DOI 10.1016/j.laa.2019.03.011 | MR 3933292 | Zbl 1411.05109
[19] D. Stevanović: Spectral Radius of Graphs. Elsevier Academic Press, Amsterdam (2015). DOI 10.1016/c2014-0-02233-2 | Zbl 1309.05001
[20] A. Yu, F. Tian: On the spectral radius of bicyclic graphs. MATCH Commun. Math. Comput. Chem. 52 (2004), 91-101. MR 2104641 | Zbl 1080.05522
[21] T. Zaslavsky: Biased graphs. I: Bias, balance, and gains. J. Comb. Theory, Ser. B 47 (1989), 32-52. DOI 10.1016/0095-8956(89)90063-4 | MR 1007712 | Zbl 0714.05057
[22] T. Zaslavsky: Matrices in the theory of signed simple graphs. Advances in Discrete Mathematics and Applications. Ramanujan Mathematical Society Lecture Notes Series 13. Ramanujan Mathematical Society, Mysore (2010), 207-229. MR 2766941 | Zbl 1231.05120
[23] T. Zaslavsky: A mathematical bibliography of signed and gain graphs and allied areas. Electron. J. Comb., Dynamic Surveys 5 (1998), Article ID DS8, 127 pages. DOI 10.37236/29 | MR 1744869 | Zbl 0898.05001
[24] T. Zaslavsky: Glossary of signed and gain graphs and allied areas. Electron. J. Comb., Dynamic Survey 5 (1998), Article ID DS9, 41 pages. DOI 10.37236/31 | MR 1744870 | Zbl 0898.05002

Affiliations:   Francesco Belardo, Maurizio Brunetti (corresponding author), Adriana Ciampella, Dipartimento di Matematica e Applicazioni "R. Caccioppoli", Università di Napoli Federico II, I-80126 Napoli, Italy, e-mail: fbelardo@unina.it; mbrunett@unina.it; ciampell@unina.it


 
PDF available at: