Strong Alliances in Graphs

Document Type : Original paper

Authors

1 Mangalore University

2 Dr. Ambedkar Institute of Technology

Abstract

For any simple connected graph $G=(V,E)$, a defensive alliance is a subset $S$ of $V$ satisfying the condition that every vertex $v\in S$ has at most one more neighbour in $V-S$ than it has in $S$. The minimum cardinality of any defensive alliance in $G$ is called the alliance number of $G$, denoted $a(G)$. In this paper, we introduce a new type of alliance number called $k$-strong alliance number and its varieties. The bounds for 1-strong alliance number in terms of different graphical parameters are determined and the characterizations of graphs with 1-strong alliance number 1, 2, and $n$ are obtained.

Keywords

Main Subjects

References

[1] R.C. Brigham, R. D. Dutton, T. W. Haynes, and S.T. Hedetniemi, Powerful alliances in graphs, Discrete Math. 309 (2009), no. 8, 2140–2147.
[2] G. Chartrand and P. Zhang, Introduction to Graph Theory, Tata McGraw-Hill Education, 2006.
[3] O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar, and R.D. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory 24 (2004), no. 2, 263–275.
[4] H. Fernau, J.A. Rodr´ıguez, and J.M. Sigarreta, Offensive r-alliances in graphs, Discrete Appl. Math. 157 (2009), no. 1, 177–182.
[5] H. Fernau and J.A. Rodriguez-Velazquez, A survey on alliances and related parameters in graphs, Electron. J. Graph Theory Appl. 2 (2014), no. 1, 70–86.
[6] F. Harary, A characterization of block-graphs, Canad. Math. Bull 6 (1963), no. 1, 1–6.
[7] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Global defensive alliances, Electron. J. Combin. 10 (2003), Article ID R47.
[8] N. Jafari Rad and H. Rezazadeh, Open alliance in graphs, International J. Math. Combin. 2 (2003), 15–21.
[9] P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin.Comput. 48 (2003), 157–177.
[10] P. Kristiansen, S.M. Hedetniemi, and S.T. Hedetniemi, Introduction to alliances in graphs, In 17th International Symposium of Computer Information Science 17 (2002), 308–312.
[11] J.A. Rodríguez, I. G. Yero, and J. M. Sigarreta, Difensive k−alliances in graphs, Appl. Math. lett. 22 (2009), no. 1, 96–100.
[12] K.H. Shafique and R. Dutton, Maximum alliance-free and minimum alliancecover sets, Congr. Numer. 162 (2003), 139–146.
[13] K.H. Shafique and R. Dutton, A tight bound on the cardinalities of maximum alliance-free and minimum alliance-cover sets, J. Combin. Math. Combin. Comput. 56 (2006), 139–145.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 1-13

Files

Share

How to cite

Statistics