On the defensive alliances in graph

Document Type: Research Paper

Authors

Department of Mathematics, Faculty of Science, Iran University of Science and Technology, Tehran, Iran.

Abstract

‎Let $ G = (V,E) $ be a graph‎. ‎We say that $ S \subseteq V $ is a defensive alliance if for every $ u \in S $‎, ‎the number of neighbors $ u $ has in $ S $ plus one (counting $ u $) is at least as large as the number of neighbors it has outside $ S $‎. ‎Then‎, ‎for every vertex $ u $ in a defensive alliance $ S $‎, ‎any attack on a single vertex by the neighbors of $ u $ in $ V-S $ can be thwarted by the neighbors of $ u $ in $ S $ and $ u $ itself‎. ‎In this paper‎, ‎we study alliances that are containing a given vertex $ u $ and study their mathematical properties‎.

Keywords

Main Subjects


[1] O. Favaron, G. Fricke, W. Go ddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar and D. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory , 24 (2004) 263{275.
[2] G. H. Fricke, L. M. Lawson, T. W. Haynes, S. M. Hedetniemi and S. T. Hedetniemi, A note on defensive alliances
in graphs, Bul l. Inst. Combin. Appl. , 38 (2003) 37{41.
[3] T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Global defensive alliances in graphs, Electron. J. Combin. , 10
(2003) 139{146.
[4] L. H. Jamieson, Algorithms and complexity for alliances and weighted alliances of different typ es, Ph. D. Thesis,
Clemson University, 2007.
[5] L. H. Jamieson, S. T. Hedetniemi and A. A. McRae, The algorithmic complexity of alliances in graphs, J. Combin.
Math. Combin. Comput. , 68 (2009) 137{150.
[6] P. Kristiansen, S. M. Hedetniemi and S. T. Hedetniemi, Alliances in graphs, J. Combin. math. Combin. Comput. ,
48 (2004) 157{177.
[7] J. A. Ro drguez-Velazquez and J. M. Sigarreta, Global defensive k -alliances in graphs, Discrete Appl. Math. , 157
(2009) 211{218.
[8] J. A. Ro drguez-Velazquez and J. M. Sigarreta, Global offensive alliances in graphs, Electron. Notes Discrete Math., 25 (2006) 157{164.
[9] J. A. Ro drguez and J. M. Sigarreta, Offensive alliances in cubic graphs, Internal. Math. Forum , 1 (2006) 1773{1782.
[10] J. A. Ro drguez and J. M. Sigarreta, Sp ectral study of alliances in graphs, Discuss. Math. Graph Theory, 27 (2007) 143{157.
[11] J. A. Ro drguez-Velazquez, I. G. Yero and J. M. Sigarreta, Defensive k -alliances in graphs, Appl. Math. Lett., 22
(2009) 96{100.
[12] J. M. Sigarreta and J. A. Ro drguez, On defensive alliance and line graphs, Appl. Math. Lett.  19 (2006) 1345{1350.
[13] J. M. Sigarreta and J. A. Ro drguez, On the global offensive alliance numb er of a graph, Discrete Appl. Math., 157 (2009) 219{226.
[14] D. B. West, Intro duction to Graph Theory, Second ed., Prentice-Hall, Upp er Saddle River, NJ, 2001.