×

Vertex-connectivity and eigenvalues of graphs with fixed girth. (English) Zbl 1428.05198

Summary: Let \(\kappa (G), g(G), \delta (G)\) and \(\Delta (G)\) denote the vertex-connectivity, the girth, the minimum degree and the maximum degree of a simple graph \(G\), and let \(\lambda_i(G), \mu_i(G)\) and \(q_i(G)\) denote the \(i\) th largest adjacency eigenvalue, Lapalcian eigenvalue and signless Laplacian eigenvalue of \(G\). We investigate functions \(f(\delta,\Delta,g, k)\) with \(\Delta\geq \delta \geq k\geq 2\) and \(g\geq 3\) such that any graph \(G\) satisfying \(\lambda_2(G)<f(\delta (G), \Delta (G), g(G), k)\) has connectivity \(\kappa (G)\geq k\). Analogues results involving the Laplacian eigenvalues and the signless Laplacian eigenvalues to describe connectivity of a graph are also presented. As corollaries, we show that for an integer \(k \geq 2\) and a simple graph \(G\) with \(n = | V(G) |\), maximum degree \(\Delta\) and minimum degree \(\delta \geq k\), the connectivity \(\kappa (G)\geq k\) if one of the following holds.
(i)
\( \lambda_2(G) < \delta - \frac{(k - 1) \operatorname{\Delta} n}{2(\delta - k + 2)(n - \delta + k - 2)} \), or
(ii)
\( \mu_{n - 1}(G) > \frac{(k - 1) \operatorname{\Delta} n}{2(\delta - k + 2)(n - \delta + k - 2)} \), or
(iii)
\(q_2(G) < 2 \delta - \frac{(k - 1) \operatorname{\Delta} n}{2(\delta - k + 2)(n - \delta + k - 2)} \).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C40 Connectivity
15A42 Inequalities involving eigenvalues and eigenvectors
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiad, A.; Brimkov, B.; Martĺnez-Rivera, X.; Zhang, S. O.J., Spectral bounds for the connectivity of regular graphs with given order, Electronic J. Linear Algebra, 34, 428-443 (2018) · Zbl 1396.05063
[2] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2012), Springer Universitext · Zbl 1231.05001
[3] Bondy, J. A.; Murty, U. S.R., Graph theory, GTM 244 (2008), Springer: Springer New York · Zbl 1134.05001
[4] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Application (1980), Academic Press · Zbl 0458.05042
[5] Chandran, S. L., Minimum cuts, girth and spectral threshold, Inf. Process. Lett., 89, 105-110 (2004) · Zbl 1183.68413
[6] Cioabă, S. M., Eigenvalues and edge-connectivity of regular graphs, Linear Algebra Appl., 432, 458-470 (2010) · Zbl 1197.05087
[7] Cioabă, S. M.; Wong, W., Edge-disjoint spanning trees and eigenvalues of regular graphs, Linear Algebra Appl., 437, 630-647 (2012) · Zbl 1242.05056
[8] Exoo, G.; Jajcay, R., Dynamic cage survey, Electron. J. Combin., DS16, 1-54 (2011)
[9] Gu, X., Connectivity and spanning trees of graphs (2013), West Virginia University, (Ph.D. Dissertation)
[10] Gu, X.; Lai, H. J.; Li, P.; Yao, S., Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs, J. Graph Theory, 81, 16-29 (2016) · Zbl 1409.05120
[11] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226/228, 593-616 (1995) · Zbl 0831.05044
[12] Kirkland, S.; Molitierno, J. J.; Neumann, M.; Shader, B. L., On graphs with equal algebraic and vertex connectivity, Linear Algebra Appl., 341, 45-56 (2002) · Zbl 0991.05071
[13] Li, G.; Shi, L., Edge-disjoint spanning trees and eigenvalues of graphs, Linear Algebra Appl., 439, 2784-2789 (2013) · Zbl 1282.05128
[14] Liu, Q.; Hong, Y.; Lai, H., Edge-disjoint spanning trees and eigenvalues, Linear Algebra Appl., 444, 146-151 (2014) · Zbl 1297.05149
[15] Liu, Q.; Hong, Y.; Gu, X.; Lai, H. J., Note on edge-disjoint spanning trees and eigenvalues, Linear Algebra Appl., 458, 128-133 (2014) · Zbl 1295.05146
[16] Mantel, W., Problem 28, Wiskundige Opgaven, 10, 60-61 (1906)
[17] O, S., Edge-connectivity in regular multigraphs from eigenvalues, Linear Algebra Appl., 491, 4-14 (2016) · Zbl 1330.05106
[18] S. O, The second largest eigenvalues and vertex-connectivity of regular multigraphs, 2016, (math.CO) 4 Oct. arXiv:1603.03960v3.; S. O, The second largest eigenvalues and vertex-connectivity of regular multigraphs, 2016, (math.CO) 4 Oct. arXiv:1603.03960v3.
[19] Tutte, W. T., A family of cubical graphs, Proc. Cambridge Philos. Soc., 43, 459-474 (1947) · Zbl 0029.42401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.