Domination subdivision numbers of trees

被引：20

作者：

Aram, H. ^{[1
]}

Sheikholeslami, S. M. ^{[1
]}

Favaron, O. ^{[2
]}

机构：

[1] Azarbaijan Univ Tarbiat Moallem, Dept Math, Tabriz, Iran

[2] Univ Paris 11, UMR 8623, LRI, F-91405 Orsay, France

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 04期

关键词：

Trees; Domination number; Domination subdivision number;

D O I：

10.1016/j.disc.2007.12.085

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A set S of vertices of a graph G = (V. E) is a dominating set if every vertex of V(G) \ S is adjacent to some vertex in S. The domination number gamma(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd(gamma)(G) is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, 1 <= sd(gamma)(T) <= 3. In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a linear algorithm for recognizing them. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：622 / 628

页数：7

共 9 条

[1] Bhattacharya A., 2002, Discussiones Mathematicae Graph Theory, V22, P335, DOI 10.7151/dmgt.1179
[2] Favaron O, 2004, UTILITAS MATHEMATICA, V66, P195
[3] Haynes T. W., 2003, Journal of Combinatorial Mathematics and Combinatorial Computing, V44, P115
[4] Haynes T. W., 2001, Discuss. Math. Graph Theory, V21, P239
[5] Total domination subdivision numbers of trees
Haynes, TW
Henning, MA
Hopkins, L
[J]. DISCRETE MATHEMATICS, 2004, 286 (03) : 195 - 202
[6] Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
[7] Karami H., AUSTRALAS J IN PRESS
[8] RELATIONS BETWEEN PACKING AND COVERING NUMBERS OF A TREE
MEIR, A
MOON, JW
[J]. PACIFIC JOURNAL OF MATHEMATICS, 1975, 61 (01) : 225 - 233
[9] Velammal S., 1997, THESIS

← 1 →