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^*

^*此作品的通讯作者

数学科学学院

East China Normal University

科研成果: 期刊稿件 › 文章 › 同行评审

3 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	1489-1494
页数	6
期刊	Graphs and Combinatorics
卷	32
期	4
DOI	https://doi.org/10.1007/s00373-015-1661-z
出版状态	已出版 - 1 7月 2016

访问文件

10.1007/s00373-015-1661-z

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

指纹

引用此