Bounding neighbor-connectivity of Abelian Cayley graphs

Lynne L. Doty

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 3, page 475-491
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Lynne L. Doty. "Bounding neighbor-connectivity of Abelian Cayley graphs." Discussiones Mathematicae Graph Theory 31.3 (2011): 475-491. <http://eudml.org/doc/270788>.

@article{LynneL2011,
abstract = {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.},
author = {Lynne L. Doty},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Cayley graphs; neighbor-connectivity bound},
language = {eng},
number = {3},
pages = {475-491},
title = {Bounding neighbor-connectivity of Abelian Cayley graphs},
url = {http://eudml.org/doc/270788},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Lynne L. Doty
TI - Bounding neighbor-connectivity of Abelian Cayley graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 3
SP - 475
EP - 491
AB - 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.
LA - eng
KW - Cayley graphs; neighbor-connectivity bound
UR - http://eudml.org/doc/270788
ER -

References

top
  1. [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. Zbl1035.05060
  2. [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. Zbl1098.05047
  3. [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. Zbl0862.05050
  4. [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. Zbl0936.05051
  5. [5] G. Gunther, Neighbour-connectivity in regular graphs, Discrete Appl. Math. 11 (1985) 233-243, doi: 10.1016/0166-218X(85)90075-7. Zbl0591.05048
  6. [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. Zbl0405.05045
  7. [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. Zbl0461.05021
  8. [8] G. Gunther, B. Hartnell and R. Nowakowski, Neighbor-connected graphs and projective planes, Networks 17 (1987) 241-247, doi: 10.1002/net.3230170208. Zbl0654.05050
  9. [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. Zbl1130.05043
  10. [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. Zbl1184.68046

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.