The Q-index and Connectivity of Graphs

Expand
  • 1 School of Mathematical Sciences, MOE-LSC, SHL-MAC, Shanghai Jiao Tong University, Shanghai 200240, China;
    2 School of Mathematics and Statistics, Central South University, Changsha 410083, Hunan, China

Received date: 2021-06-20

  Revised date: 2022-04-17

  Online published: 2024-06-12

Supported by

Xiao-Dong Zhang is partly supported by the National Natural Science Foundation of China (Nos. 11971311, 12161141003, and 12026230) and Science and Technology Commission of Shanghai Municipality (No. 22JC1403600); Li-Hua Feng and Wei-Jun Liu are partly supported by the National Natural Science Foundation of China (Nos. 11871479, 12071484) and Hunan Provincial Natural Science Foundation (Nos. 2020JJ4675, 2018JJ2479).

Abstract

A connected graph G is said to be k -connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted. In this paper, for a connected graph G with sufficiently large order, we present a tight sufficient condition for G with fixed minimum degree to be k -connected based on the Q-index. Our result can be viewed as a spectral counterpart of the corresponding Dirac-type condition.

Cite this article

Peng-Li Zhang, Li-Hua Feng, Wei-Jun Liu, Xiao-Dong Zhang . The Q-index and Connectivity of Graphs[J]. Journal of the Operations Research Society of China, 2024 , 12(2) : 505 -519 . DOI: 10.1007/s40305-022-00427-3

References

[1] Brualdi, R.A., Solheid, E.S.:On the spectral radius of complementary acyclic matrices of zeros and ones. SIAM J. Algebra. Discret. Method 7, 265-272(1986)
[2] Berman, A., Zhang, X.-D.:On the spectral radius of graphs with cut vertices. J. Combin. Theory Ser. B. 83, 233-240(2001)
[3] Liu, H.Q., Lu, M., Tian, F.:On the spectral radius of graphs with cut edges. Linear Algebra Appl. 389, 139-145(2004)
[4] Feng, L.H., Cao, J.X., Liu, W.J., Ding, S.F., Liu, H.:The spectral radius of edge chromatic critical graphs. Linear Algebra Appl. 492, 78-88(2016)
[5] Zhang, X.-D.:The signless Laplacian spectral radius of graphs with given degree sequence. Discret. Appl. Math. 157(13), 2928-2937(2009)
[6] Zhou, B.:Signless Laplacian spectral radius and Hamiltonicity. Linear Algebra Appl. 432(2/3), 566-570(2010)
[7] Huo, B.F., Li, X.L., Shi, Y.T.:Complete solution to a conjecture on the maximal energy of unicyclic graphs. Eur. J. Combin. 32(5), 662-673(2011)
[8] Li, J., Li, X.L., Shi, Y.T.:On the maximal energy tree with two maximum degree vertices. Linear Algebra Appl. 435(9), 2272-2284(2011)
[9] Li, X.L., Shi, Y.T., Wei, M.Q., Li, J.:On a conjecture about tricyclic graphs with maximal energy. MATCH Commun. Math. Comput. Chem. 72(1), 183-214(2014)
[10] Zhang, M.J., Li, S.C.:Extremal Halin graphs with respect to the signless Laplacian spectra. Discret. Appl. Math. 213, 207-218(2016)
[11] Nikiforov, V.:The spectral radius of graphs without paths and cycles of specified length. Linear Algebra Appl. 432(9), 2243-2256(2010)
[12] Fiedler, M., Nikiforov, V.:Spectral radius and Hamiltonicity of graphs. Linear Algebra Appl. 432(9), 2170-2173(2010)
[13] Feng, L.H., Zhang, P.L., Liu, H., Liu,W.J., Liu, M.M., Hu, Y.Q.:Spectral conditions for some graphical properties. Linear Algebra Appl. 524, 182-198(2017)
[14] Feng, L.H., Zhang, P.L., Liu, W.J.:Spectral radius andk-connectedness of graphs. Monatsh. Math. 185, 651-661(2018)
[15] Feng, L.H., Zhu, X.M., Liu, W.J.:Wiener index, Harary index and graph properties. Discret. Appl. Math. 223, 72-83(2017)
[16] Li, Y.W., Liu, Y., Peng, X.:Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree. Linear Multilinear Algebra 66(10), 2011-2023(2018)
[17] Liu,W.J.,Huang, Z., Li,Y.T., Feng, L.H.:A sufficient Q-spectral conditionfor a graph to be β-deficient involving minimum degree. Discret. Appl. Math. 265, 158-167(2019)
[18] Liu, W.J., Liu, M.M., Feng, L.H.:Spectral conditions for graphs to be β-deficient involving minimum degree. Linear Multilinear Algebra 66(4), 792-802(2018)
[19] Liu, W.J., Liu, M.M., Zhang, P.L., Feng, L.H.:Spectral conditions for graphs to be k-Hamiltonian or k-path-coverable. Discuss. Math. Graph Theory 40(1), 161-179(2020)
[20] Lu, M., Liu, H.Q., Tian, F.:Spectral radius and Hamiltonian graphs. Linear Algebra Appl. 437(7), 1670-1674(2012)
[21] Ning, B., Ge, J.:Spectral radius and Hamiltonian properties of graphs. Linear Multilinear Algebra 63(8), 1520-1530(2015)
[22] Wu, Q.F., Zhang, P.L., Feng, L.H.:Connectivity and spectral radius of graphs. Ars Combin. 142, 197-206(2019)
[23] Zhou, Q.N., Wang, L.G., Lu, Y.:Some sufficient conditions onk-connected graphs. Appl. Math. Comput. 325, 332-339(2018)
[24] Zhou, Q.N.,Wang, L.G., Lu, Y.:Signless Laplacian spectral conditionsfor Hamilton-connected graphs with large minimum degree. Linear Algebra Appl. 592, 48-64(2020)
[25] Fiedler, M.:Algebraic connectivity of graphs. Czechoslov. Math. J. 23(98), 298-305(1973)
[26] Chandran, S.L.:Minimum cuts, girth and spectral threshold. Inf. Process. Lett. 89(3), 105-110(2004)
[27] Cioabă, S.M.:Eigenvalues and edge-connectivity of regular graphs. Linear Algebra Appl. 432, 458-470(2010)
[28] Gu, X.F., Lai, H.-J., Li, P., Yao, S.M.:Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs. J. Graph Theory 81(1), 16-29(2016)
[29] Liu, H.Q., Lu, M., Tian, F.:Edge-connectivity and (signless) Laplacian eigenvalue of graphs. Linear Algebra Appl. 439(12), 3777-3784(2013)
[30] O,S., Cioaba, S.M.:Edge-connectivity, eigenvalues, and matchings in regular graphs. SIAM J. Discret. Math. 24(4), 1470-1481(2010)
[31] Bollobás, B.:Extremal Graph Theory. Academic Press, New York (1978)
[32] Nikiforov, V.:Spectral radius and Hamiltonicity of graphs with large minimum degree. Czechoslov. Math. J. 66(141), 925-940(2016)
[33] Li, B.L., Ning, B.:Spectral analogues of Erdős's and Moon-Moser's theorems on Hamilton cycles. Linear Multilinear Algebra 64(11), 2252-2269(2016)
[34] Feng, L.H., Yu, G.H.:On the three conjectures involving the signless Laplacian spectral radius of graphs. Publ. Inst. Math.(Beograd)85(99), 35-38(2009)
[35] Hong, Z.M., Xia, Z.J., Chen, F., Volkmann, L.:Sufficient conditions for graphs to bek-connected, maximally connected and super-connected. Complexity 1-11 https://doi.org/10.1155/2021/5588146(2021)
[36] Hong, Y., Zhang, X.-D.:Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees. Discret. Math. 296, 187-197(2005)
Options
Outlines

/