Global alliances and independent domination in some classes of graphs (Q1010858)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Global alliances and independent domination in some classes of graphs |
scientific article |
Statements
Global alliances and independent domination in some classes of graphs (English)
0 references
7 April 2009
0 references
Summary: A dominating set \(S\) of a graph \(G\) is a global (strong) defensive alliance if for every vertex \(v\in S\), the number of neighbors \(v\) has in \(S\) plus one is at least (greater than) the number of neighbors it has in \(V\setminus S\). The dominating set \(S\) is a global (strong) offensive alliance if for every vertex \(v\in V\setminus S\), the number of neighbors \(v\) has in \(S\) is at least (greater than) the number of neighbors it has in \(V\setminus S\) plus one. The minimum cardinality of a global defensive (strong defensive, offensive, strong offensive) alliance is denoted by \(\gamma_a(G) (\gamma_{\hat a}(G), \gamma_o(G), \gamma_{\hat o}(G))\). We compare each of the four parameters \(\gamma_a, \gamma_{\hat a}, \gamma_o, \gamma_{\hat o}\) to the independent domination number \(i\). We show that \(i(G)\leq \gamma ^2_a(G)-\gamma_a(G)+1\) and \(i(G)\leq \gamma_{\hat{a}}^2(G)-2\gamma_{\hat{a}}(G)+2\) for every graph; \(i(G)\leq \gamma ^2_a(G)/4 +\gamma_a(G)\) and \(i(G)\leq \gamma_{\hat{a}}^2(G)/4 +\gamma_{\hat{a}}(G)/2\) for every bipartite graph; \(i(G)\leq 2\gamma_a(G)-1\) and \(i(G)=3\gamma_{\hat{a}}(G)/2 -1\) for every tree and describe the extremal graphs; and that \(\gamma_o(T)\leq 2i(T)-1\) and \(i(T)\leq \gamma_{\hat o}(T)-1\) for every tree. We use a lemma stating that \(\beta(T)+2i(T)\geq n+1\) in every tree \(T\) of order \(n\) and independence number \(\beta(T)\).
0 references
dominating set
0 references
global defensive alliance
0 references
strong defensive alliance
0 references
global offensive alliance
0 references
strong offensive alliance
0 references
independent domination number
0 references
extremal graphs
0 references