Strategic balance in graphs

详细信息    查看全文

• 作者：Robert Lewoń^a ; ^{lewon.robert@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Anna Małafiejska^b ; ^{anna@animima.org" class="auth_mail" title="E-mail the corresponding author} ; Michał Małafiejski^a ; ^{michal@animima.org" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Global alliance ; Alliance partitioning number ; Strategic balance
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 July 2016
• 年：2016
• 卷：339
• 期：7
• 页码：1837-1847
• 全文大小：530 K

文摘

For a given graph G$G$, a nonempty subset S$S$ contained in 13d7302cd9a" title="Click to view the MathML source">V(G)$V\left(G\right)$ is an alliance   iff for each vertex d09ac44a133181aa090d800" title="Click to view the MathML source">v∈S$v\in S$ there are at least as many vertices from the closed neighbourhood of v$v$ in S$S$ as in V(G)−S$V\left(G\right)-S$. An alliance is global   if it is also a dominating set of G$G$. The alliance partition number   of G$G$ was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of 13d7302cd9a" title="Click to view the MathML source">V(G)$V\left(G\right)$ such that each set is an alliance. Similarly, in Eroh and Gera (2008) the global alliance partition number is defined for global alliances, where the authors studied the problem for (binary) trees.

In the paper we introduce a new concept of strategic balance   in graphs: for a given graph G$G$, determine whether there is a partition of vertex set 13d7302cd9a" title="Click to view the MathML source">V(G)$V\left(G\right)$ into three subsets N$N$, S$S$ and I$I$ such that both N$N$ and S$S$ are global alliances. We give a survey of its general properties, e.g., showing that a graph G$G$ has a strategic balance iff its global alliance partition number equals at least 2. We construct a linear time algorithm for solving the problem in trees (thus giving an answer to the open question stated in Eroh and Gera (2008)) and studied this problem for many classes of graphs: paths, cycles, wheels, stars, complete graphs and complete k$k$-partite graphs. Moreover, we prove that this problem is NP$\mathcal{NP}$-complete for graphs with a degree bounded by 4 and state an open question regarding subcubic graphs.