Offensive r-alliances in graphs

DOI10.1016/J.DAM.2008.06.001zbMATH Open1200.05157DBLPjournals/dam/FernauRS09arXivmath/0703598OpenAlexW2072894899WikidataQ57974438 ScholiaQ57974438MaRDI QIDQ1003773FDOQ1003773

Authors: Henning Fernau, Juan Ángel Rodríguez, Jose M. Sigarreta 

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let $G=(V,E)$ be a simple graph. For a nonempty set $XsubsetV,$ and a vertex $vinV,$ $delt{a}_X(v)$ denotes the number of neighbors $v$ has in $X.$ A nonempty set $SsubsetV$ is an emph{offensive $r$-alliance} in $G$ if $$ $forallvinpartial(S),$ where $partial(S)$ denotes the boundary of $S$. An offensive $r$-alliance $S$ is called emph{global} if it forms a dominating set. The emph{global offensive $r$-alliance number} of $G$, denoted by $gamm{a}_r^o(G)$, is the minimum cardinality of a global offensive $r$-alliance in $G$. We show that the problem of finding optimal (global) offensive $r$-alliances is NP-complete and we obtain several tight bounds on $gamm{a}_r^o(G)$.

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

Recommendations

• Offensive alliances in graphs
• scientific article; zbMATH DE number 5777940
• On global offensive \(k\)-alliances in graphs
• Offensive alliances in cubic graphs
• A note on the global offensive alliances in graphs
• On the defensive alliances in graph
• Defensive \(k\)-alliances in graphs
• Partitioning a graph into offensive \(k\)-alliances
• scientific article; zbMATH DE number 6843424
• Defensive alliances in graphs

zbMATH Keywords

computational complexitydominationoffensive alliancesalliances in graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Global defensive alliances in graphs
• Global alliances in planar graphs
• On defensive alliances and line graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral study of alliances in graphs
• An upper bound for thek-domination number of a graph
• On the global offensive alliance number of a graph
• Global offensive alliances in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Offensive alliances in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Global alliances and independence in trees

Cited In (27)

• Partitioning a graph into offensive \(k\)-alliances
• Global powerful \(r\)-alliances and total \(k\)-domination in graphs
• On defensive alliances and strong global offensive alliances
• Upper bounds on the global offensive alliances in graphs
• Saturated boundary \(k\)-alliances in graphs
• Global offensive alliances in graphs and random graphs
• Partitioning a graph into defensive \(k\)-alliances
• Structural parameterization of alliance problems
• Title not available (Why is that?)
• Gromov hyperbolic cubic graphs
• Offensive alliances in graphs
• Alliances in graphs of bounded clique-width
• Global defensive alliances in star graphs
• On global offensive \(k\)-alliances in graphs
• Global offensive alliances in graphs
• Defensive alliances in graphs
• Globally minimal defensive alliances
• Offensive alliances in signed graphs
• Algorithms and Complexity of Alliances in Graphs
• Alliances and Related Domination Parameters
• A study of monopolies in graphs
• Global defensive alliances in the lexicographic product of paths and cycles
• New families of Laplacian borderenergetic graphs
• Alliances in graphs: parameters, properties and applications -- a survey
• On the global offensive alliance number of a graph
• Alliance free and alliance cover sets
• Partitioning a graph into global powerful \(k\)-alliances

This page was built for publication: Offensive \(r\)-alliances in graphs

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