A new bound for neighbor-connectivity of abelian Cayley graphs (Q2497468)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new bound for neighbor-connectivity of abelian Cayley graphs |
scientific article |
Statements
A new bound for neighbor-connectivity of abelian Cayley graphs (English)
0 references
4 August 2006
0 references
A graph \(\Gamma\) has neighbor-connectivity \(k\), written as \(\text{NC}(\Gamma)=k\), when \(k\) is the size of a smallest subset \(B\) of \(V(\Gamma)\) such that the deletion of \(B\) and all vertices adjacent to a vertex in \(B\) leaves a graph that is empty, complete, or disconnected. It is known that \(\text{ NC}(\Gamma)\leq\kappa(\Gamma)\) [\textit{G. Gunther, B. Hartnell} and \textit{R. Nowakowski}, Networks 17, 241--247 (1987; Zbl 0654.05050)], where \(\kappa\) denotes the usual connectivity. Doty shows that if \(\Gamma\) is an \(r\)-valent Cayley graph of an abelian group, then \(\text{{NC}}(\Gamma)\leq\lceil r/2\rceil+2\) and \(\text{ NC}(\Gamma)\leq\lceil3\kappa/4\rceil+2\).
0 references
subversion strategy
0 references
Cayley graph
0 references