Global alliances in planar graphs
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 \).
- Global defensive \(k\)-alliances in graphs
- On the global offensive alliance number of a graph
- Offensive \(r\)-alliances in graphs
- Alliances in graphs: parameters, properties and applications -- a survey
- Partitioning a graph into global powerful k-alliances
- Saturated boundary \(k\)-alliances in graphs
- Global edge alliances in graphs
- Global defensive sets in graphs
- Global defensive alliances in trees
- Alliances and Related Domination Parameters
- Small Alliances in Graphs
- Alliances and bisection width for planar graphs
- Lower bounds for global alliances of planar graphs
- Partitioning a graph into defensive k-alliances
- Minority sets in graphs
- Minimum-cardinality global defensive alliances in general graphs
- Majority sets in graphs
This page was built for publication: Global alliances in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2469302)
