Mathematics – Combinatorics
Scientific paper
2012-04-02
Mathematics
Combinatorics
18 pages
Scientific paper
A global offensive alliance in a graph $G$ is a set $S$ of vertices with the property that every vertex not belonging to $S$ has at least one more neighbor in $S$ than it has outside of $S$. The global offensive alliance number of $G$, $\gamma_o(G)$, is the minimum cardinality of a global offensive alliance in $G$. A set $S$ of vertices of a graph $G$ is a dominating set for $G$ if every vertex not belonging to $S$ has at least one neighbor in $S$. The domination number of $G$, $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. In this work we obtain closed formulas for the global offensive alliance number of several families of Cartesian product graphs, we also prove that $\gamma_o(G\square H)\ge \frac{\gamma(G)\gamma_o(H)}{2}$ for any graphs $G$ and $H$ and we show that if $G$ has an efficient dominating set, then $\gamma_o(G\square H)\ge \gamma(G)\gamma_o(H).$ Moreover, we present a Vizing-like conjecture for the global offensive alliance number and we prove it for several families of graphs.
Rodriguez-Velazquez Juan A.
Yero González I.
No associations
LandOfFree
Computing global offensive alliances in Cartesian product graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing global offensive alliances in Cartesian product graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing global offensive alliances in Cartesian product graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-510477