On Minimum Algebraic Connectivity of Tricyclic Graphs

Document Type : Original Scientific Paper

Authors

‎Faculty of Mathematical Science, ‎Department of Pure Mathematics,‎ ‎University of Kashan,‎ ‎Kashan 87317-51167‎, ‎I. R. Iran

10.22052/mir.2024.253568.1437

Abstract

‎Consider a simple‎, ‎undirected graph $ G=(V,E)$‎, ‎where $A$ represents the adjacency matrix and $Q$ represents the Laplacian matrix of $G$‎. ‎The second smallest eigenvalue of Laplacian matrix of $G$ is called the algebraic connectivity of $G$‎. ‎In this article‎, ‎we present a Python program for studying the Laplacian eigenvalues of a graph‎. ‎Then‎, ‎we determine the unique graph of minimum algebraic connectivity in the set of all tricyclic graphs‎.

Keywords

Main Subjects


[1] F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, American Mathematical Soc., 1997
[2] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, Johann Ambrosius Barth Verlag, Heidelberg, Leipzig, 1995.
[3] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003) 241 - 272, https://doi.org/10.1016/S0024-3795(03)00483-X.
[4] W. N. Anderson Jr and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141 - 145, https://doi.org/10.1080/03081088508817681.
[5] M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J. 25 (1975) 619 - 633, https://doi.org/10.21136/CMJ.1975.101357.
[6] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197-198 (1994) 143 - 176, https://doi.org/10.1016/0024-3795(94)90486-3.
[7] M. Fiedler, Algebraic connectivity of graphs, Czechoslov. Math. J. 23 (1973) 298 - 305, https://doi.org/10.21136/CMJ.1973.101168.
[8] N. M. M. de Abreu, Old and new results on algebraic connectivity of graphs, Linear Algebra Appl. 423 (2007) 53 - 73,
https://doi.org/10.1016/j.laa.2006.08.017.
[9] R. Nasiri, H. R. Ellahi, A. Gholami and G. H. Fath-Tabar, The irregularity and total irregularity of Eulerian graphs, Iranian J. Math. Chem. 9 (2018) 101 - 111, https://doi.org/10.22052/IJMC.2018.44232.1153.
[10] D. Vukicevic and Z. Yarahmadi, One-alpha descriptor, Iranian J. Math. Chem. 9 (2018) 179-186, https://doi.org/ 10.22052/IJMC.2018.118091.1342.
[11] D. Cvetkovic, M. Doob, I. Gutman and A. Torgašev, Recent Results in the Theory of Graph Spectra, Ann. Discrete Math. 36, North-Holland, Amsterdam, 1988.
[12] J. Li, J. M. Guo and W. C. Shiu, The orderings of bicyclic graphs and connected graphs by algebraic connectivity, Electron. J. Combin. 17 (2010) Research Paper 162, https://doi.org/10.37236/434.
[13] A. Z. Abdian, A. R. Ashrafi, L. W. Beineke, M. R. Oboudi and G. H. Fath-Tabar, Monster graphs are determined by their Laplacian spectra, Rev. Un. Mat. Argentina 63 (2022) 413-424, https://doi.org/10.33044/revuma.1769.
[14] M. Arabzadeh, G. H. Fath–Tabar, H. Rasoli and A. Tehranian, Estrada and L-estrada indices of a graph and their relationship with the number of spanning trees, MATCH Commun. Math. Comput. Chem. 90 (2023) 787 - 798, https://doi.org/10.46793/match.90-3.787A.
[15] G. K. Gök, Kirchhoff index and Kirchhoff energy, Iranian J. Math. Chem. 13 (2022) 175 - 185, https://doi.org/10.22052/IJMC.2022.246278.1619.
[16] T. Vetrik, Degree-based function index of graphs with given connectivity, Iranian J. Math. Chem. 14 (2023) 183 - 194, https://doi.org/ 10.22052/IJMC.2023.252646.1699.
[17] M. Taheri-Dehkordi and G. H. Fath-Tabar, On the number of perfect star packing and perfect pseudo matching in some fullerene graphs, Iranian J. Math. Chem. 14 (2023) 7 - 18, https://doi.org/10.22052/IJMC.2022.248451.1669.
[18] M. Arabzadeh, G. H. Fath-Tabar, H. Rasouli and A. Tehranian, On the difference between Laplacian and signless Laplacian coefficients of a graph and its applications on the fullerene graphs, Iranian J. Math. Chem. 15 (2024)
39 - 50, https://doi.org/10.22052/IJMC.2024.254123.1808.
[19] J. -Y. Shao, J. -M. Guo and H. -Y. Shan, The ordering of trees and connected graphs by their algebraic connectivity, Linear Algebra Appl. 428 (2008) 1421-1438, https://doi.org/10.1016/j.laa.2007.08.031.