For the notion of neighbor-connectivity in graphs whenever a vertex is subverted the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. Doty has sharpened that bound in abelian Cayley graphs to approximately (1/2)κ. The main result of this paper is the constructive development of an alternative, and often tighter, bound for abelian Cayley graphs through the use of an auxiliary graph determined by the generating set of the abelian Cayley graph.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1559,
author = {Lynne L. Doty},
title = {Bounding neighbor-connectivity of Abelian Cayley graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {31},
year = {2011},
pages = {475-491},
zbl = {1229.05113},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1559}
}
Lynne L. Doty. Bounding neighbor-connectivity of Abelian Cayley graphs. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 475-491. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1559/
[000] [1] I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319-328, doi: 10.1016/S0166-218X(02)00573-5. | Zbl 1035.05060
[001] [2] L.L. Doty, A new bound for neighbor-connectivty of abelian Cayley graphs, Discrete Math. 306 (2006) 1301-1316, doi: 10.1016/j.disc.2005.09.018. | Zbl 1098.05047
[002] [3] L.L. Doty, R.J. Goldstone and C.L. Suffel, Cayley graphs with neighbor connectivity one, SIAM J. Discrete Math. 9 (1996) 625-642, doi: 10.1137/S0895480194265751. | Zbl 0862.05050
[003] [4] R.J. Goldstone, The structure of neighbor disconnected vertex transitive graphs, Discrete Math. 202 (1999) 73-100, doi: 10.1016/S0012-365X(98)00348-3. | Zbl 0936.05051
[004] [5] G. Gunther, Neighbour-connectivity in regular graphs, Discrete Appl. Math. 11 (1985) 233-243, doi: 10.1016/0166-218X(85)90075-7. | Zbl 0591.05048
[005] [6] G. Gunther and B. Hartnell, On minimizing the effects of betrayals in a resistance movement, in: Proc. 8th Manitoba Conf. on Numerical Mathematics and Computing (Winnipeg, Manitoba, Canada, 1978) 285-306. | Zbl 0405.05045
[006] [7] G. Gunther and B. Hartnell, Optimal k-secure graphs, Discrete Appl. Math. 2 (1980) 225-231, doi: 10.1016/0166-218X(80)90042-6. | Zbl 0461.05021
[007] [8] G. Gunther, B. Hartnell and R. Nowakowski, Neighbor-connected graphs and projective planes, Networks 17 (1987) 241-247, doi: 10.1002/net.3230170208. | Zbl 0654.05050
[008] [9] J. Huang and J.-M. Xu, The bondage numbers and efficient dominations of vertex-transitive graphs, Discrete Math. 308 (2008) 571-582, doi: 10.1016/j.disc.2007.03.027. | Zbl 1130.05043
[009] [10] N. Obradovic, J. Peters and G. Ruzic, Efficient domination in circulant graphs with two chord lengths, Information Processing Letters 102 (2007) 253-258, doi: 10.1016/j.ipl.2007.02.004. | Zbl 1184.68046