Edge lifting and total domination in graphs

被引：1

作者：

Desormeaux, Wyatt J. ^{[1
]}

Haynes, Teresa W. ^{[2
]}

Henning, Michael A. ^{[1
]}

机构：

[1] Univ Johannesburg, Dept Math, ZA-2006 Auckland Pk, South Africa

[2] E Tennessee State Univ, Dept Math & Stat, Johnson City, TN 37614 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2013年 / 25卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

Edge lifting; Edge splitting; Total domination; VERTEX CRITICAL GRAPHS; RELATIVE COMPLEMENTS; DIAMETER; RESPECT;

D O I：

10.1007/s10878-011-9416-0

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Let u and v be vertices of a graph G, such that the distance between u and v is two and x is a common neighbor of u and v. We define the edge lift of uv off x as the process of removing edges ux and vx while adding the edge uv to G. In this paper, we investigate the effect that edge lifting has on the total domination number of a graph. Among other results, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. Trees for which every possible edge lift increases the total domination number are characterized.

引用

页码：47 / 59

页数：13

共 22 条

[1] Chen XG, 2008, ARS COMBINATORIA, V88, P289
[2] Desormeaux W.J., 2011, Quaest. Math, V34, P1
[3] Total domination stable graphs upon edge addition
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
[J]. DISCRETE MATHEMATICS, 2010, 310 (24) : 3446 - 3454
[4] Total domination critical and stable graphs upon edge removal
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
[J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) : 1587 - 1592
[5] The diameter of total domination vertex critical graphs
Goddard, W
Haynes, TW
Henning, MA
van der Merwe, LC
[J]. DISCRETE MATHEMATICS, 2004, 286 (03) : 255 - 261
[6] Hanson D, 2003, UTILITAS MATHEMATICA, V63, P89
[7] Haynes T.W., 1998, Chapman & Hall/CRC Pure and Applied Mathematics
[8] Haynes TW, 2002, ARS COMBINATORIA, V64, P169
[9] Haynes TW, 2001, ARS COMBINATORIA, V59, P117
[10] Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]

← 1 2 3 →