Upper Bounds for the Paired-Domination Numbers of Graphs

Changhong Lu; Chao Wang; Kan Wang

doi:10.1007/s00373-015-1661-z

Upper Bounds for the Paired-Domination Numbers of Graphs

Changhong Lu
, Chao Wang
, Kan Wang^*

^*Corresponding author for this work

School of Mathematical Sciences

East China Normal University

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

3 Scopus citations

Abstract

A set S⊆ V is 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 a graph G, denoted by γ_p_r(G) , is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree δ(G) ≥ 3 , then γ_p_r(G) ≤ 4 n/ 7. In this paper, we confirm this conjecture for k-regular graphs with k≥ 4.

Original language	English
Pages (from-to)	1489-1494
Number of pages	6
Journal	Graphs and Combinatorics
Volume	32
Issue number	4
DOIs	https://doi.org/10.1007/s00373-015-1661-z
State	Published - 1 Jul 2016

Keywords

Dominating set
Paired-domination
Regular graph

Access to Document

10.1007/s00373-015-1661-z

Cite this

@article{15c41a1c8eed4a6fa48b395b624c9a50,

title = "Upper Bounds for the Paired-Domination Numbers of Graphs",

abstract = "A set S⊆ V is a paired-dominating set if every vertex in V\textbackslash{} S has at least one neighbor in S and the subgraph induced by S 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 of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree δ(G) ≥ 3 , then γpr(G) ≤ 4 n/ 7. In this paper, we confirm this conjecture for k-regular graphs with k≥ 4.",

keywords = "Dominating set, Paired-domination, Regular graph",

author = "Changhong Lu and Chao Wang and Kan Wang",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Japan.",

year = "2016",

month = jul,

day = "1",

doi = "10.1007/s00373-015-1661-z",

language = "英语",

volume = "32",

pages = "1489--1494",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "4",

}

TY - JOUR

T1 - Upper Bounds for the Paired-Domination Numbers of Graphs

AU - Lu, Changhong

AU - Wang, Chao

AU - Wang, Kan

PY - 2016/7/1

Y1 - 2016/7/1

N2 - A set S⊆ V is 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 a graph G, denoted by γpr(G) , is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree δ(G) ≥ 3 , then γpr(G) ≤ 4 n/ 7. In this paper, we confirm this conjecture for k-regular graphs with k≥ 4.

AB - A set S⊆ V is 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 a graph G, denoted by γpr(G) , is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree δ(G) ≥ 3 , then γpr(G) ≤ 4 n/ 7. In this paper, we confirm this conjecture for k-regular graphs with k≥ 4.

KW - Dominating set

KW - Paired-domination

KW - Regular graph

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

U2 - 10.1007/s00373-015-1661-z

DO - 10.1007/s00373-015-1661-z

M3 - 文章

AN - SCOPUS:84949510002

SN - 0911-0119

VL - 32

SP - 1489

EP - 1494

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -

Upper Bounds for the Paired-Domination Numbers of Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this