Paired versus double domination in K 1,r -free graphs

Paul Dorbec, Bert Hartnell, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ pr(G), is the minimum cardinality of a paired-dominating set in G. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ ×2(G). A claw-free graph is a graph that does not contain K 1,3 as an induced subgraph. Chellali and Haynes (Util. Math. 67:161-171, 2005) showed that for every claw-free graph G, we have γ pr(G)≤ γ×2 (G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K 1,r as an induced subgraph, then γpr(G) ≤ (2r2-6r+6/r(r-1) γ ×2(G).

Original languageEnglish
Pages (from-to)688-694
Number of pages7
JournalJournal of Combinatorial Optimization
Volume27
Issue number4
DOIs
Publication statusPublished - May 2014

Keywords

  • Claw-free
  • Double domination
  • Paired-domination

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Paired versus double domination in K 1,r -free graphs'. Together they form a unique fingerprint.

Cite this