Upper paired‐domination in claw‐free graphs

Upper paired‐domination in claw‐free graphs

0.00 Avg rating0 Votes
Article ID: iaor20116925
Volume: 22
Issue: 2
Start Page Number: 235
End Page Number: 251
Publication Date: Aug 2011
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: pareto-optimality
Abstract:

A set S of vertices in a graph G is a paired‐dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired‐dominating set of G is the upper paired‐domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw‐free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized.

Reviews

Required fields are marked *. Your email address will not be published.