کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651117 | 1342521 | 2006 | 16 صفحه PDF | دانلود رایگان |
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 κκ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κκ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2⌈3κ/4⌉+2 for abelian Cayley graphs.
Journal: Discrete Mathematics - Volume 306, Issue 13, 6 July 2006, Pages 1301–1316