The total bondage numbers and efficient total dominations of vertex-transitive graphs

被引：2
作者：
Hu, Fu-Tao [1 ]
Li, Lu [1 ]
Liu, Jia-Bao [2 ]
机构：
[1] Anhui Univ, Sch Math Sci, Hefei 230601, Anhui, Peoples R China
[2] Anhui Jianzhu Univ, Sch Math & Phys, Hefei 230601, Anhui, Peoples R China
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2018年 / 332卷
基金：
中国国家自然科学基金;
关键词：
Total dominating set; Efficient total dominating set; Total bondage number; Vertex-transitive graphs; CAYLEY-GRAPHS; PERFECT DOMINATION; SETS;
D O I：
10.1016/j.amc.2018.03.046
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The total domination number of a graph G without isolated vertices is the minimum number of vertices that dominate all vertices in G. The total bondage number of G is the minimum number of edges whose removal enlarges the total domination number. In this paper, we establish a tight lower bound for the total bondage number of a vertex-transitive graph. We also obtain upper bounds for regular graphs by investigating the relation between the total bondage number and the efficient total domination. As applications, we study the total bondage numbers for some circulant graphs and toroidal meshes by characterizing the existence of efficient total dominating sets in these graphs. (C) 2018 Elsevier Inc. All rights reserved.
引用
收藏
页码：35 / 41
页数：7
相关论文
共 23 条
  • [1] Bondy J., 2008, GRADUATE TEXTS MATH
  • [2] On the bondage number of planar and directed graphs
    Carlson, Kelli
    Develin, Mike
    [J]. DISCRETE MATHEMATICS, 2006, 306 (8-9) : 820 - 826
  • [3] Efficient open domination in Cayley graphs
    Chelvam, T. Tamizh
    Mutharasu, Sivagnanam
    [J]. APPLIED MATHEMATICS LETTERS, 2012, 25 (10) : 1560 - 1564
  • [4] TOTAL DOMINATION IN GRAPHS
    COCKAYNE, EJ
    DAWES, RM
    HEDETNIEMI, ST
    [J]. NETWORKS, 1980, 10 (03) : 211 - 219
  • [5] Efficient dominating sets in Cayley graphs
    Dejter, IJ
    Serra, O
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) : 319 - 328
  • [6] Dejter IJ, 2008, AUSTRALAS J COMB, V42, P99
  • [7] THE BONDAGE NUMBER OF A GRAPH
    FINK, JF
    JACOBSON, MS
    KINCH, LF
    ROBERTS, J
    [J]. DISCRETE MATHEMATICS, 1990, 86 (1-3) : 47 - 57
  • [8] Gavlas H., 2002, Electron. Notes Discrete Math, V11, P681, DOI DOI 10.1016/S1571-0653(04)00113-1
  • [9] Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
  • [10] Haynes TW., 1998, FUNDAMENTALS DOMINAT
123