2012/04/02 by Ismael G. Yero, Yero, Ismael G., Juan A. Rodríguez-Velázquez +1
Mathematics · #05C69 #05C70 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69 #msc:05C70 #msc:05C76
paper · pdf · doi:10.48550/arxiv.1204.0494
15 pages
arxiv created 2012/07/25 · arxiv updated 2012/07/26
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, γ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, γ(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 γo(G\square H)≥ (γ(G)γo(H))/(2) for any graphs G and H and we show that if G has an efficient dominating set, then γo(G\square 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.