Signed bicyclic graphs with minimal index

Document Type : Original paper

Authors

Dipartimento di Matematica e Applicazioni R. Caccioppoli. Universita' di Napoli Federico II

Abstract

The index λ1(Γ) of a signed graph Γ=(G,σ) is just the largest eigenvalue of its adjacency matrix. For any n⩾4 we identify the signed graphs achieving the minimum index in the class of signed bicyclic graphs with n vertices. Apart from the n=4 case, such graphs are obtained by considering a starlike tree with four branches of suitable length (i.e.\ four distinct paths joined at their end vertex u) with two additional negative independent edges pairwise joining the four vertices adjacent to u. As a by-product, all signed bicyclic graphs containing  a theta-graph and whose index is less than 2 are detected.

Keywords

Main Subjects

References

[1] S. Akbari, F. Belardo, F. Heydari, M. Maghasedi, and M. Souri, On the largest eigenvalue of signed unicyclic graphs, Linear Algebra Appl. 581 (2019), 145--162.
[2] S. Akbari, S. Dalvandi, F. Heydari, and M. Maghasedi, Signed complete graphs with maximum index, Discuss. Math. Graph Theory 40, no. 2, 393--403.
[3] F. Belardo, M. Brunetti, and A. Ciampella, Signed bicyclic graphs minimizing the least laplacian eigenvalue, Linear Algebra Appl. 557 (2018), 201--233.
[4] F. Belardo, M. Brunetti, and A. Ciampella, Unbalanced unicyclic and bicyclic graphs with extremal spectral radius,
Czechoslovak Math. J. 71 (2021), no. 2, 417--433.
[5] F. Belardo, M. Brunetti, V. Trevisan, and J.-F. Wang, On Quipus whose signless Laplacian index does not exceed 4:5, (submitted).
[6] F. Belardo, E.M. Li Marzi, and S.K.  Simić, Combinatorial approach for computing the characteristic polynomial of a matrix, Linear Algebra Appl. 433 (2010), no. 8-10, 1513--1523.
[7] F. Belardo and Y. Zhou, Signed graphs with extremal least laplacian eigenvalue, Linear Algebra Appl. 497 (2016), 167--180.
[8] T. Biyikoğu and J. Leydold, Graphs of given order and size and minimum algebraic connectivity, Linear algebra Appl. 436 (2012), no. 7, 2067--2077.
[9] M. Brunetti and Z. Stanić, Ordering signed graphs with large index, (submitted).
[10] M. Brunetti and Z. Stanić, Unbalanced signed graphs with extremal spectral radius or index, (submitted).
[11] D. Cvetković, P. Rowlinson, and S.K. Simić, Signless Laplacians of  nite graphs, Linear Algebra Appl. 423 (2007), no. 1, 155--171.
[12] D.M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs-Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
[13] E. Ghorbani and A. Majidi, Signed graphs with maximal index, Discrete Math. 344 (2021), no. 8, 112463.
[14] C. He, Y. Li, H. Shan, and W. Wang, On the index of unbalanced signed bicyclic graphs, Comput. Appl. Math. 40 (2021), no. 4, 1--14.
[15] D.P. Jacobs and V. Trevisan, Locating the eigenvalues of trees, Linear Algebra Appl. 434 (2011), no. 1, 81--88.
[16] C.R. Johnson and B.D. Sutton, Hermitian matrices, eigenvalue multiplicities, and eigenvector components, SIAM J. Matrix Anal. Appl. 26 (2004), no. 2, 390--399.
[17] T. Koledin and Z. Stanić, Connected signed graphs of  xed order, size, and number of negative edges with maximal index, Linear Multilinear Algebra 65 (2017), no. 11, 2187--2198.
[18] K.L. Patra and A.K. Lal, The e ect on the algebraic connectivity of a tree by grafting or collapsing of edges, Linear Algebra Appl. 428 (2008), no. 4, 855--864.
[19] M. Souri, F. Heydari, and M. Maghasedi, Maximizing the largest eigenvalues of signed unicyclic graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 2, ID: 2050016.
[20] Z. Stanić, Integral regular net-balanced signed graphs with vertex degree at most four, Ars Math. Contemp. 17 (2019), no. 1, 103--114.
[21] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), no. 1, 47--74.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 207-241

Files

Share

How to cite

Statistics