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 $\lambda_1(\Gamma)$ of a signed graph $\Gamma=(G,\sigma)$ is just the largest eigenvalue of its adjacency matrix. For any $n \geqslant 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