Paired-domination in claw-free graphs with minimum degree at least three

Changhong Lu; Bing Wang; Kan Wang; Yana Wu

doi:10.1016/j.dam.2018.09.005

Paired-domination in claw-free graphs with minimum degree at least three

Changhong Lu, Bing Wang, Kan Wang, Yana Wu

School of Mathematical Sciences

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

5 Scopus citations

Abstract

Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is called a paired-dominating set if every vertex in V∖S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set of G. We show that γ _pr (G)≤4n∕7 if G is a claw-free graph of order n with minimum degree at least three. The statement partly confirms the conjecture proposed by Goddard and Henning in 2009.

Original language	English
Pages (from-to)	250-259
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	257
DOIs	https://doi.org/10.1016/j.dam.2018.09.005
State	Published - 31 Mar 2019

Keywords

Claw-free graph
Dominating set
Paired-domination

Access to Document

10.1016/j.dam.2018.09.005

Cite this

@article{dd758c1af7394242a1e86058985425af,

title = "Paired-domination in claw-free graphs with minimum degree at least three",

abstract = " Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is called a paired-dominating set if every vertex in V∖S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired-dominating set of G. We show that γ pr (G)≤4n∕7 if G is a claw-free graph of order n with minimum degree at least three. The statement partly confirms the conjecture proposed by Goddard and Henning in 2009.",

keywords = "Claw-free graph, Dominating set, Paired-domination",

author = "Changhong Lu and Bing Wang and Kan Wang and Yana Wu",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2019",

month = mar,

day = "31",

doi = "10.1016/j.dam.2018.09.005",

language = "英语",

volume = "257",

pages = "250--259",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Paired-domination in claw-free graphs with minimum degree at least three

AU - Lu, Changhong

AU - Wang, Bing

AU - Wang, Kan

AU - Wu, Yana

PY - 2019/3/31

Y1 - 2019/3/31

N2 - Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is called a paired-dominating set if every vertex in V∖S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired-dominating set of G. We show that γ pr (G)≤4n∕7 if G is a claw-free graph of order n with minimum degree at least three. The statement partly confirms the conjecture proposed by Goddard and Henning in 2009.

AB - Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is called a paired-dominating set if every vertex in V∖S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired-dominating set of G. We show that γ pr (G)≤4n∕7 if G is a claw-free graph of order n with minimum degree at least three. The statement partly confirms the conjecture proposed by Goddard and Henning in 2009.

KW - Claw-free graph

KW - Dominating set

KW - Paired-domination

UR - https://www.scopus.com/pages/publications/85055252981

U2 - 10.1016/j.dam.2018.09.005

DO - 10.1016/j.dam.2018.09.005

M3 - 文章

AN - SCOPUS:85055252981

SN - 0166-218X

VL - 257

SP - 250

EP - 259

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Paired-domination in claw-free graphs with minimum degree at least three

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this