کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421195 | 684158 | 2013 | 10 صفحه PDF | دانلود رایگان |
A global offensive alliance in a graph GG is a set SS of vertices with the property that every vertex not belonging to SS has at least one more neighbor in SS than it has outside of SS. The global offensive alliance number of GG, γo(G)γo(G), is the minimum cardinality of a global offensive alliance in GG. A set SS of vertices of a graph GG is a dominating set for GG if every vertex not belonging to SS has at least one neighbor in SS. The domination number of GG, γ(G)γ(G), is the minimum cardinality of a dominating set of GG. 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 GG and HH and we show that if GG 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.
Journal: Discrete Applied Mathematics - Volume 161, Issues 1–2, January 2013, Pages 284–293