Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Global alliances and independent domination in some classes of graphs. | Global alliances and independent domination in some classes of graphs Odile Favaron LRI UMR 8623 Univ Paris-Sud F-91405 Orsay France CNRS F-91405 Orsay of@ Submitted Nov 21 2007 Accepted Sep 22 2008 Published Sep 29 2008 Mathematics Subject Classification 05C69 Abstract A dominating set S of a graph G is a global strong defensive alliance if for every vertex v 2 S the number of neighbors v has in S plus one is at least greater than the number of neighbors it has in V S. The dominating set S is a global strong offensive alliance if for every vertex v 2 V S the number of neighbors v has in S is at least greater than the number of neighbors it has in V S plus one. The minimum cardinality of a global defensive strong defensive offensive strong offensive alliance is denoted by 72 G 72 G 7o G 70 G . We compare each of the four parameters 72 72 7o 7o to the independent domination number i. We show that i G 72 G - 7a G 1 and i G 72 G - 272 G 2 for every graph i G 72 G 4 72 G and i G 72 G 4 72 G 2 for every bipartite graph i G 272 G 1 and i G 372 G 2 1 for every tree and describe the extremal graphs and that 7o T 2i T 1 and i T 7õ T 1 for every tree. We use a lemma stating that fi T 2i T n 1 in every tree T of order n and independence number fi T . Keywords independence domination alliance bipartite graph tree. 1 Introduction We consider simple graphs G V G E G with vertex set V G edge set E G order n G V G and size m G E G V E n m when no ambiguity is possible . The degree in G of a vertex v is denoted by dG v or simply d v and the number of neighbors of v in a subset S of V by ds v . A subset S of vertices is dominating if every vertex of Vn S has at least one neighbor in S and independent if no two vertices of S are adjacent. It is well known that a dominating THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R123 1 set is independent if and only if it is a maximal independent set and that in every graph 7 G i G p G where 7 G and i G are respectively the minimum .
