On the global offensive alliance number of a graph
From MaRDI portal
Publication:1003662
DOI10.1016/J.DAM.2008.02.007zbMath1191.05072arXivmath/0602432OpenAlexW2161713493WikidataQ57974455 ScholiaQ57974455MaRDI QIDQ1003662
Publication date: 4 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: An offensive alliance in a graph $Gamma=(V,E)$ is a set of vertices $Ssubset V$ where for every vertex $v$ in its boundary it holds that the majority of vertices in $v$'s closed neighborhood are in $S$. In the case of strong offensive alliance, strict majority is required. An alliance $S$ is called global if it affects every vertex in $V�ackslash S$, that is, $S$ is a dominating set of $Gamma$. The offensive alliance number $a_o(Gamma)$ (respectively, strong offensive alliance number $a_{hat{o}}(Gamma)$) is the minimum cardinality of an offensive (respectively, strong offensive) alliance in $Gamma$. The global offensive alliance number $gamma_o(Gamma)$ and the global strong offensive alliance number $gamma_{hat{o}}(Gamma)$ are defined similarly. Clearly, $a_o(Gamma)le gamma_o(Gamma)$ and $a_{hat{o}}(Gamma)le gamma_{hat{o}}(Gamma)$. It was shown in [Discuss. Math. Graph Theory, 24 (2004), no. 2, 263-275] that $ a_o(Gamma)le frac{2n}{3}$ and $ a_{hat{o}}(Gamma)le frac{5n}{6}$, where $n$ denotes the order of $Gamma$. In this paper we obtain several tight bounds on $gamma_o(Gamma)$ and $gamma_{hat{o}}(Gamma)$ in terms of several parameters of $Gamma$. For instance, we show that $frac{2m+n}{3Delta+1} le gamma_o(Gamma)le frac{2n}{3}$ and $frac{2(m+n)}{3Delta+2} legamma_{hat{o}}(Gamma)le frac{5n}{6}$, where $m$ denotes the size of $Gamma$ and $Delta$ its maximum degree (the last upper bound holds true for all $Gamma$ with minimum degree greatest or equal to two).
Full work available at URL: https://arxiv.org/abs/math/0602432
Cites Work
Related Items (26)
On structural parameterizations of the offensive alliance problem ⋮ A study of monopolies in graphs ⋮ On global offensive \(k\)-alliances in graphs ⋮ Partitioning a graph into global powerful \(k\)-alliances ⋮ Globally minimal defensive alliances ⋮ Secure sets and their expansion in cubic graphs ⋮ Global defensive alliances in the lexicographic product of paths and cycles ⋮ Parameterized intractability of defensive alliance problem ⋮ Partitioning a graph into offensive \(k\)-alliances ⋮ Alliance free and alliance cover sets ⋮ On defensive alliances and strong global offensive alliances ⋮ Alliances in graphs: parameters, properties and applications -- a survey ⋮ Alliance free sets in Cartesian product graphs ⋮ Upper bounds on the global offensive alliances in graphs ⋮ Global offensive alliances in graphs and random graphs ⋮ Integer programming approach to static monopolies in graphs ⋮ Partitioning a graph into defensive \(k\)-alliances ⋮ Boundary defensive \(k\)-alliances in graphs ⋮ Global defensive \(k\)-alliances in graphs ⋮ Offensive \(r\)-alliances in graphs ⋮ A note on the global offensive alliances in graphs ⋮ Alliances and Related Domination Parameters ⋮ Defensive alliances in graphs ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Saturated boundary \(k\)-alliances in graphs ⋮ Linear time algorithms for weighted offensive and powerful alliances in trees
This page was built for publication: On the global offensive alliance number of a graph
