Upper Bounds on the Paired Domination Subdivision Number of a Graph

被引：6

作者：

Egawa, Yoshimi ^{[1
]}

Furuya, Michitaka ^{[1
]}

Takatou, Masanori ^{[1
]}

机构：

[1] Tokyo Univ Sci, Dept Math Informat Sci, Shinjuku Ku, Tokyo 1628601, Japan

来源：

GRAPHS AND COMBINATORICS | 2013年 / 29卷 / 04期

关键词：

Paired domination number; Paired domination subdivision number; Tree;

D O I：

10.1007/s00373-012-1162-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by gamma (pr)(G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then . We also characterize trees T such that sd gamma pr (T) >= vertical bar V(T)vertical bar/2.

引用

页码：843 / 856

页数：14

共 9 条

[1]

DIESTEL R., 2012, Grad. Texts in Math., V173

[2] Paired-Domination Subdivision Numbers of Graphs [J].

Favaron, O. ;

Karami, H. ;

Sheikholeslami, S. M. .

GRAPHS AND COMBINATORICS, 2009, 25 (04) :503-512

[3]

Haynes T. W., 2004, Discussiones Mathematicae Graph Theory, V24, P457, DOI 10.7151/dmgt.1244

[4]

Haynes T. W., 2003, Journal of Combinatorial Mathematics and Combinatorial Computing, V44, P115

[5]

Haynes T. W., 2001, Discuss. Math. Graph Theory, V21, P239

[6]

Haynes T.W., 1995, C NUM, P65

[7]

Haynes TW, 1998, NETWORKS, V32, P199, DOI 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO

[8]

2-F

[9]

Velammal S., 1997, Ph.D. Thesis

← 1 →