Portal de Periódicos da CAPES

Cayley Graphs with Neighbor Connectivity One

1996; Society for Industrial and Applied Mathematics; Volume: 9; Issue: 4 Linguagem: Inglês

10.1137/s0895480194265751

1095-7146

Lynne L. Doty, Richard Goldstone, C Suffel,

Advanced Graph Theory Research

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.