2015/11/16 by Mohamed Bouzefrane, Bouzefrane, Mohamed, Saliha Ouatiki +1
Mathematics · #05C69 #05C75 #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #G.2.2 #acm:05C69 #acm:05C75 #math.CO #msc:05C69 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1511.04884
11 pages, 1 figure
arxiv created 2015/11/16 · arxiv updated 2015/11/17
For a graph G=(V,E), a set S⊆ V is a dominating set if every vertex in V-S has at least a neighbor in S. A dominating set S is a global offensive alliance if for each vertex v in V-S at least half the vertices from the closed neighborhood of v are in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the global offensive alliance number γo(G) is the minimum cardinality of a global offensive alliance of G. We show that if G is a connected unicycle graph of order n with l(G) leaves and s(G) support vertices then γo(G)≥(n-l(G)+s(G))/(3). Moreover, we characterize all extremal unicycle graphs attaining this bound.