Offensive alliances in cubic graphs

DOI10.12988/IMF.2006.06152MaRDI QIDQ3433453zbMATH OpenOpenAlexFDO

Authors

Publication date 30 April 2007

Published in International Mathematical Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610023

zbMATH Keywords

domination numberglobal allianceindependence number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: An offensive alliance in a graph $Gamma=(V,E)$ is a set of vertices $SsubsetV$ 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 $$, that is, $S$ is a dominating set of $Gamma$. The global offensive alliance number $gamm{a}_o(Gamma)$ (respectively, global strong offensive alliance number $gamm{a}_{hato}(Gamma)$) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in $Gamma$. If $Gamma$ has global independent offensive alliances, then the emph{global independent offensive alliance number} $gamm{a}_i(Gamma)$ is the minimum cardinality among all independent global offensive alliances of $Gamma$. In this paper we study mathematical properties of the global (strong) alliance number of cubic graphs. For instance, we show that for all connected cubic graph of order $n$, ${\displaystyle }$frac{2n}{5}le gamma_i(Gamma)le frac{n}{2}le gamma_{hat{o}}(Gamma)le frac{3n}{4} le gamma_{hat{o}}({cal L}(Gamma))=gamma_{o}({cal L}(Gamma))le n,${\displaystyle }$ where $calL(Gamma)$ denotes the line graph of $Gamma$. All the above bounds are tight.

Recommendations

• On the global offensive alliance number of a graph
• Global offensive alliances in graphs
• Global offensive alliance numbers in graphs with emphasis on trees
• scientific article; zbMATH DE number 5777940
• Independence and global offensive alliance in graphs

Cited in

(20)

• Global defensive \(k\)-alliances in graphs
• On the global offensive alliance number of a graph
• Offensive \(r\)-alliances in graphs
• Global defensive alliances in star graphs
• Defensive k-alliances in graphs
• Alliances in graphs: parameters, properties and applications -- a survey
• A note on the global offensive alliances in graphs
• Partitioning a graph into global powerful k-alliances
• Upper bounds on the global offensive alliances in graphs
• An inequality on global alliances for trees
• Linear time algorithms for weighted offensive and powerful alliances in trees
• On defensive alliances and strong global offensive alliances
• Some bounds on global alliances in trees
• Global offensive alliances in graphs and random graphs
• Global dual k-alliance in cubic graphs
• scientific article; zbMATH DE number 5777940 (Why is no real title available?)
• A study of monopolies in graphs
• Global strong defensive alliances of Sierpiński-like graphs
• Global offensive alliances and groupies in heterogeneous random graphs
• Boundary defensive k-alliances in graphs

This page was built for publication: Offensive alliances in cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3433453)