Idioma:

Spectral Threshold for Extremal Cyclic Edge-Connectivity

Aksoy, Sinan G. ; Kempton, Mark ; Young, Stephen J.

Graphs and combinatorics, 2021-11, Vol.37 (6), p.2079-2093 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Spectral Threshold for Extremal Cyclic Edge-Connectivity
Autor: Aksoy, Sinan G. ; Kempton, Mark ; Young, Stephen J.
Assuntos: Combinatorics ; Connectivity ; Eigenvalues ; Engineering Design ; fault tolerance ; graph analysis ; Graph theory ; Mathematics ; MATHEMATICS AND COMPUTING ; Mathematics and Statistics ; Original Paper ; spectral graph theory ; Upper bounds
É parte de: Graphs and combinatorics, 2021-11, Vol.37 (6), p.2079-2093
Notas: USDOE
AC05-76RL01830
PNNL-SA-151831
Descrição: The universal cyclic edge-connectivity of a graph G is the least k such that there exists a set of k edges whose removal disconnects G into components where every component contains a cycle. We show that for graphs of minimum degree at least 3 and girth g at least 4, the universal cyclic edge-connectivity is bounded above by ( Δ - 2 ) g where Δ is the maximum degree. We then prove that if the second eigenvalue of the adjacency matrix of a d -regular graph of girth g ≥ 4 is sufficiently small, then the universal cyclic edge-connectivity is ( d - 2 ) g , providing a spectral condition for when this upper bound on universal cyclic edge-connectivity is tight.
Editor: Tokyo: Springer Japan
Idioma: Inglês

Links

Voltar para lista de resultados