Edge lifting and total domination in graphs

被引：0
|
作者：
Wyatt J. Desormeaux
Teresa W. Haynes
Michael A. Henning
机构：
[1] University of Johannesburg,Department of Mathematics
[2] East Tennessee State University,Department of Mathematics and Statistics
来源：
Journal of Combinatorial Optimization | 2013年 / 25卷
关键词：
Edge lifting; Edge splitting; Total domination;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：12
相关论文
共 50 条
  • [21] Total Domination in Partitioned Graphs
    Frendrup, Allan
    Vestergaard, Preben Dahl
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2009, 25 (02) : 181 - 196
  • [22] Total Domination in Regular Graphs
    Hoppen, Carlos
    Mansan, Giovane
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 523 - 533
  • [23] TOTAL ROMAN DOMINATION IN GRAPHS
    Ahangar, Hossein Abdollahzadeh
    Henning, Michael A.
    Samodivkin, Vladimir
    Yero, Ismael G.
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2016, 10 (02) : 501 - 517
  • [24] Chromatic total domination in graphs
    Balamurugan, S.
    Anitha, M.
    Eswari, M. Angala
    Kalaiselvi, S.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2019, 22 (05) : 745 - 751
  • [25] Total domination stability in graphs
    Henning, Michael A.
    Krzywkowski, Marcin
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 246 - 255
  • [26] Girth and Total Domination in Graphs
    Henning, Michael A.
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 199 - 214
  • [27] From Total Roman Domination in Lexicographic Product Graphs to Strongly Total Roman Domination in Graphs
    Almerich-Chulia, Ana
    Cabrera Martinez, Abel
    Hernandez Mira, Frank Angel
    Martin-Concepcion, Pedro
    SYMMETRY-BASEL, 2021, 13 (07):
  • [28] Double domination edge critical graphs
    Haynes, Teresa W.
    Thacker, Derrick
    UTILITAS MATHEMATICA, 2009, 78 : 139 - 149
  • [29] Relating the total {2}-domination number with the total domination number of graphs
    Villamar, I. Rios
    Cabrera-Martinez, A.
    Sanchez, J. L.
    Sigarreta, J. M.
    DISCRETE APPLIED MATHEMATICS, 2023, 333 : 90 - 95
  • [30] Total Dominator Colorings and Total Domination in Graphs
    Michael A. Henning
    Graphs and Combinatorics, 2015, 31 : 953 - 974
12345