Computing global offensive alliances in Cartesian product graphs
A global offensive alliance in a graph G G is a set S S of vertices with the property that every vertex not belonging to S S has at least one more neighbor in S S than it has outside of S S . The global offensive alliance number of G G , ?o(G) ? o ( G ) , is the minimum cardinality of a global offensive alliance in G G . A set S S of vertices of a graph G G is a dominating set for G G if every vertex not belonging to S S has at least one neighbor in S S . The domination number of G G , ?(G) ? ( G ) , is the minimum cardinality of a dominating set of G 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 ? o ( G ? H ) ? ? ( G ) ? o ( H ) 2 for any graphs G G and H H and we show that if G G has an efficient dominating set, then ?o(G?H)??(G)?o(H) ? o ( G ? H ) ? ? ( G ) ? o ( H ) . Moreover, we present a Vizing-like conjecture for the global offensive alliance number and we prove it for several families of graphs.
global offensive alliances cartesian product graphs domination