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.
| Original language | English |
|---|---|
| Pages (from-to) | 47-59 |
| Number of pages | 13 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 25 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Jan 2013 |
Keywords
- Edge lifting
- Edge splitting
- Total domination
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics