Semipaired Domination in Claw-Free Cubic Graphs

Michael A. Henning; Pawaton Kaemawichanurat

doi:10.1007/s00373-018-1916-6

Semipaired Domination in Claw-Free Cubic Graphs

Michael A. Henning, Pawaton Kaemawichanurat

Mathematics and Applied Mathematics

King Mongkut's University of Technology Thonburi

Research output: Contribution to journal › Article › peer-review

15 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 language	English
Pages (from-to)	819-844
Number of pages	26
Journal	Graphs and Combinatorics
Volume	34
Issue number	4
DOIs	https://doi.org/10.1007/s00373-018-1916-6
Publication status	Published - 1 Jul 2018

Keywords

Claw-free
Cubic
Paired-domination
Semipaired domination number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-018-1916-6

Cite this

@article{25f17b9eddb94fee9dde55fddf9ce304,

title = "Semipaired Domination in Claw-Free Cubic Graphs",

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.",

keywords = "Claw-free, Cubic, Paired-domination, Semipaired domination number",

author = "Henning, {Michael A.} and Pawaton Kaemawichanurat",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Japan KK, part of Springer Nature.",

year = "2018",

month = jul,

day = "1",

doi = "10.1007/s00373-018-1916-6",

language = "English",

volume = "34",

pages = "819--844",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "4",

}

TY - JOUR

T1 - Semipaired Domination in Claw-Free Cubic Graphs

AU - Henning, Michael A.

AU - Kaemawichanurat, Pawaton

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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.

AB - 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.

KW - Claw-free

KW - Cubic

KW - Paired-domination

KW - Semipaired domination number

UR - http://www.scopus.com/inward/record.url?scp=85048763494&partnerID=8YFLogxK

U2 - 10.1007/s00373-018-1916-6

DO - 10.1007/s00373-018-1916-6

M3 - Article

AN - SCOPUS:85048763494

SN - 0911-0119

VL - 34

SP - 819

EP - 844

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -

Semipaired Domination in Claw-Free Cubic Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this