Connectivity and eigenvalues of graphs with given girth or clique number

DOI10.1016/J.LAA.2020.08.015zbMATH Open1459.05173arXiv2001.00740OpenAlexW3059273804MaRDI QIDQ2226409FDOQ2226409

Authors: Zhen-Mu Hong, Hong-Jian Lai, Zheng-Jiang Xia 

Publication date: 12 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Let $kapp{a}^{\prime }(G)$, $kappa(G)$, $m{u}_{n-1}(G)$ and $m{u}_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $kgeq2$ and $rgeq2$, and any simple graph $G$ of order $n$ with minimum degree $deltageqk$, girth $ggeq3$ and clique number $omega(G)leqr$, the edge-connectivity $kapp{a}^{\prime }(G)geqk$ if $m{u}_{n-1}(G)geqfrac(k-1)nN(delta,g)(n-N(delta,g))$ or if $m{u}_{n-1}(G)geqfrac(k-1)nvarphi(delta,r)(n-varphi(delta,r))$, where $N(delta,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $delta$-regular simple graph with girth $g$, and $varphi(delta,r)=maxdelta+1,lfloorfracrdeltar-1floor$. Analogue results involving $m{u}_{n-1}(G)$ and $fracm{u}_1(G)m{u}_{n-1}(G)$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended.

Full work available at URL: https://arxiv.org/abs/2001.00740

Recommendations

• Vertex-connectivity and eigenvalues of graphs with fixed girth
• Vertex-connectivity and eigenvalues of graphs
• On connectivity in graphs with given clique number
• Eigenvalues and edge-connectivity of regular graphs
• On eigenvalue multiplicity and the girth of a graph
• Eigenvalues, Laplacian eigenvalues, and Hamiltonian connectivity of graphs
• Eigenvalues and clique partitions of graphs
• Eigenvalues and the diameter of graphs
• The least eigenvalue of graphs with given connectivity
• Edge-connectivity, eigenvalues, and matchings in regular graphs

zbMATH Keywords

eigenvalueclique numbergirthalgebraic connectivityedge-connectivityvertex-connectivity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Connectivity (05C40)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Spectra of graphs
• Interlacing eigenvalues and graphs
• Title not available (Why is that?)
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge-disjoint spanning trees and eigenvalues of graphs
• Edge-disjoint spanning trees and eigenvalues
• On graphs with equal algebraic and vertex connectivity
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Note on edge-disjoint spanning trees and eigenvalues
• Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs
• Edge-disjoint spanning trees and eigenvalues of regular graphs
• Edge-connectivity and (signless) Laplacian eigenvalue of graphs
• Eigenvalues and edge-connectivity of regular graphs
• Edge-connectivity in regular multigraphs from eigenvalues
• Minimum cuts, girth and a spectral threshold
• Vertex-connectivity and eigenvalues of graphs
• Spectral bounds for the connectivity of regular graphs with given order
• Vertex-connectivity and eigenvalues of graphs with fixed girth
• Spanning tree packing number and eigenvalues of graphs with given girth
• The second largest eigenvalue and vertex-connectivity of regular multigraphs

Cited In (11)

• Edge-connectivity and (signless) Laplacian eigenvalue of graphs
• Vertex-connectivity and eigenvalues of graphs
• Vertex-connectivity and eigenvalues of graphs with fixed girth
• On connectivity in graphs with given clique number
• Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number
• Minimum cuts, girth and a spectral threshold
• On the (signless Laplacian) spectral radius of minimally \(k\)-(edge)-connected graphs for small \(k\)
• Effects on the algebraic connectivity of weighted graphs under edge rotations
• Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs
• Interpretable random forest model for identification of edge 3-uncolorable cubic graphs
• Spectral bounds for the vulnerability parameters of graphs

This page was built for publication: Connectivity and eigenvalues of graphs with given girth or clique number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226409)