Refined connectivity properties of abelian Cayley graphs (Q1273101)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Refined connectivity properties of abelian Cayley graphs |
scientific article |
Statements
Refined connectivity properties of abelian Cayley graphs (English)
0 references
15 March 1999
0 references
A set \(U\) of edges of a connected graph \(G\) is called a restricted cutset if \(G-U\) is disconnected and contains no trivial component \(K_1\). The restricted edge connectivity \(\lambda'(G)\) is the minimum size of restricted cutsets in \(G\). Let \(G=\text{Cay} (\Gamma,S)\) be a connected abelian Cayley graph. Then \(\lambda'(G) =| \Gamma |/2\), if \(S\) contains exactly one element \(x\) of order 2 such that \(\langle S-x\rangle \neq\Gamma \wedge| \Gamma |\leq 4| S|-4\), and \(\lambda'(G)=2| S|-2\), otherwise. The high order edge connectivity \(N_i\), \(i\geq 1\), is the number of edge cutsets of size \(i\). To determine all \(N_i\), \(i\geq 1\), for a general graph is NP-hard. The authors determine \(N_i\), \(1\leq i\leq \lambda'-1\), for any connected abelian Cayley graph.
0 references
restricted cutset
0 references
restricted edge connectivity
0 references
abelian Cayley graph
0 references
high order edge connectivity
0 references
NP-hard
0 references