Upper paired-domination in claw-free graphs |
| |
Authors: | Paul?Dorbec Email author" target="_blank">Michael?A?HenningEmail author |
| |
Institution: | 1.Equipe GraphComb—ERTé “Maths à modeler”, LRI,Université Paris Sud 11,Orsay,France;2.School of Mathematical Sciences,University of KwaZulu-Natal,Pietermaritzburg,South Africa |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|