Cayley Graphs with Neighbor Connectivity One
Lynne L. Doty, Richard Goldstone, Charles L. Suffel · SIAM Journal on Discrete Mathematics · 1996
We give an algebraic characterization of the generating sets of Cayley graphs with neighbor connectivity equal to one for a class of Cayley graphs that includes the Cayley graphs of all abelian groups. We also show that the determination of the neighbor connectivity of a graph is NP-hard.