Global alliances in planar graphs (Q2469302): Difference between revisions

The global defensive alliance number \(\gamma _{a}(G)\) (resp., global strong defensive alliance number \(\gamma _{as}(G)\)) is the minimum cardinality of any global defensive alliance (resp., global strong defensive alliance) in \(G\). In this paper it is shown that if \(G\) has order \(n\) and \(S\) is a global defensive alliance in \(G\) such that the subgraph \(\langle S\rangle\) induced by \(S\) is planar, then: if \(n>6\), then \(| S| \geq \lceil (n+12)/8\rceil \); if \(\langle S\rangle\) is triangle-free then \(| S| \geq \lceil (n+8)/6\rceil \); if \(n>4\) and \(S\) is strong, then \(| S| \geq \lceil (n+12)/7\rceil \), if \(S\) is strong and \(\langle S\rangle\) is triangle-free then \(| S| \geq \lceil (n+8)/5\rceil \). In particular, if \(G\) is planar, these inequalities hold for \(\gamma _{a}(G)\) and in some cases, these bounds are attained. In the case when \(\langle S\rangle\) is planar connected with \(f\) faces then \(| S| \geq \lceil (n-2f+4)/4 \rceil \); if \(S\) is also strong then \(| S| \geq \lceil (n-2f+4)/3\rceil \). In the case when \(| S| >2\), \(\langle S\rangle\) is planar and its minimum degree is at least \(k\) or \(\langle S\rangle\) is triangle-free and its minimum degree is at least \(k\) corresponding lower bounds are obtained. If \(T\) is a tree of order \(n\) and \(S\) is a global defensive alliance in \(T\) such that \(\langle S\rangle\) has \(c\) components, then \(| S| \geq \lceil (n+2c)/4\rceil \); if \(S\) is strong, then \(| S| \geq \lceil (n+2c)/3\rceil \). Similar results are also deduced for global offensive alliances or for dual alliances (alliances which are both defensive and offensive). If \(\gamma _{ad}\) and \(\gamma _{ads}\) denote the corresponding numbers for dual alliances, it is shown e.g., that if \(T\) is a tree of order \(n\) then \(\gamma _{ad}(T)\geq \lceil (n+2)/4\rceil \) and \(\gamma _{ads}(T)\geq \lceil (2n+7)/5\rceil \).