Semipaired Domination in Claw-Free Cubic Graphs

Michael A. Henning, Pawaton Kaemawichanurat

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

A subset S of vertices in a graph G is a dominating set if every vertex in V(G) \ S is adjacent to a vertex in S. If the graph G has no isolated vertex, then a semipaired dominating set of G is a dominating set of G with the additional property that the set S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a claw-free, connected, cubic graph of order n≥ 10 , then γpr2(G)≤25n.

Original languageEnglish
Pages (from-to)819-844
Number of pages26
JournalGraphs and Combinatorics
Volume34
Issue number4
DOIs
Publication statusPublished - 1 Jul 2018

Keywords

  • Claw-free
  • Cubic
  • Paired-domination
  • Semipaired domination number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Semipaired Domination in Claw-Free Cubic Graphs'. Together they form a unique fingerprint.

Cite this