|
Chan et al. classified the2-extendable abelian Cayley graphs and posed the problem ofcharacterizing all 2-extendable Cayley graphs. We first show that a connected bipartite Cayley (vertex-transitive) graph is 2-extendable if and only if it is not a cycle. %Thereafter, the 2-extendability of Cayley graphs on specific groups, such as Dihedral group, Dicylic group, Generalized xing{generalized} dihedral group, Quasi-abelian groups and etc, has been investigated. We first show that all $k$-regular ($kgeq 3$) bipartite Cayley graphs are 2-extendable. It is known that a non-bipartite Cayley (vertex-transitive) graph is 2-extendable when it is of minimum degree at least 5. %Hence the 2-extendability of Cayley graphs of minimum degrees 3 and 4 are left.We next characterize all 2-extendable cubic non-bipartite Cayley graphs and obtain that: a cubic non-bipartite Cayley graph with girth $g$ is2-extendable if and only if $ggeq 4$ and it doesn't isomorphic to $Z_{4n}(1,4n-1,2n)$ or $Z_{4n+2}(2,4n,2n+1)$ with $ngeq 2$. Indeed, we prove a more stronger result that a cubic non-bipartite vertex-transitive graph with girth $g$ is2-extendable if and only if $ggeq 4$ and it doesn't isomorphic to $Z_{4n}(1,4n-1,2n)$ or $Z_{4n+2}(2,4n,2n+1)$ with $ngeq 2$ or the Petersen graph. |
|
Keywords:Cayley graph; vertex-transitive graph; $2$-extendablility; matching; edge-connectivity. |
|