Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chen X, Sohn MY (2008) A note on the total domination vertex critical graphs. Ars Comb 88:289–294
Cockayne EJ, Dawes RM, Hedetniemi ST (1980) Total domination in graphs. Networks 10:211–219
Desormeaux WJ, Hall AJ, Haynes TW, Koessler D, Langston MA, Rickett SA, Scott H (2011a) Edge lifting and domination in graphs. Bull Inst Combin Appl 63:77–86
Desormeaux WJ, Haynes TW, Henning MA (2011b) Domination edge lift critical trees. Quaest Math 34:1–12
Desormeaux WJ, Haynes TW, Henning MA (2010a) Total domination stable graphs upon edge addition. Discrete Math 310:3446–3454
Desormeaux WJ, Haynes TW, Henning MA (2010b) Total domination critical and stable graphs upon edge removal. Discrete Appl Math 158:1587–1592
Goddard W, Haynes TW, Henning MA, van der Merwe LC (2004) The diameter of total domination vertex critical graphs. Discrete Math 286:255–261
Hanson D, Wang P (2003) A note on extremal total domination edge critical graphs. Util Math 63:89–96
Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Dekker, New York
Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Domination in graphs: advanced topics. Dekker, New York
Haynes TW, Henning MA, van der Merwe LC (2001) Domination and total domination critical trees with respect to relative complements. Ars Comb 59:117–127
Haynes TW, Henning MA, van der Merwe LC (2002) Total domination critical graphs with respect to relative complements. Ars Comb 64:169–179
Haynes TW, Mynhardt CM, van der Merwe LC (1998c) Total domination edge critical graphs. Util Math 54:229–240
Henning MA (2009) Recent results on total domination in graphs: a survey. Discrete Math 309:32–63
Loizeaux M, van der Merwe LC (2006) A total domination vertex critical graph of diameter two. Bull Inst Comb Appl 48:63–65
Lovász L (1993) Combinatorial problems and exercises, 2nd edn. North-Holland, New York
Lovász L (1974) In: Lecture, conference of graph theory, Prague
van der Merwe LC, Haynes TW, Mynhardt CM (1999) 3-domination critical graphs with arbitrary independent domination numbers. Bull Inst Combin Appl 27:85–88
van der Merwe LC, Haynes TW, Mynhardt CM (2001) Total domination edge critical graphs with maximum diameter. Discuss Math, Graph Theory 21:187–205
van der Merwe LC, Haynes TW, Mynhardt CM (2003) Total domination edge critical graphs with minimum diameter. Ars Comb 66:79–96
van der Merwe LC (1999) Total domination edge critical graphs. PhD thesis, University of South Africa
van der Merwe LC, Loizeaux M (2007) \(4\sb t\)-critical graphs with maximum diameter. J Comb Math Comb Comput 60:65–80
van der Merwe LC, Loizeaux M (2009) Bounds on the order of 4-critical graphs with diameter two. Util Math 78:107–119
Wang CX, Fei PS (2007) On maximum total domination vertex critical graphs. Math Appl (Wuhan) 20:191–195
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Desormeaux, W.J., Haynes, T.W. & Henning, M.A. Edge lifting and total domination in graphs. J Comb Optim 25, 47–59 (2013). https://doi.org/10.1007/s10878-011-9416-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-011-9416-0