Upper paired-domination in claw-free graphs

Paul Dorbec, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)235-251
Number of pages17
JournalJournal of Combinatorial Optimization
Issue number2
Publication statusPublished - Aug 2011
Externally publishedYes


  • Claw-free graphs
  • Minimum degree
  • Upper paired-domination

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Upper paired-domination in claw-free graphs'. Together they form a unique fingerprint.

Cite this