Disjoint Paired-Dominating sets in Cubic Graphs

被引：1
作者：
Bacso, Gabor [1 ]
Bujtas, Csilla [2 ,3 ]
Tompkins, Casey [4 ,5 ]
Tuza, Zsolt [2 ,4 ]
机构：
[1] Hungarian Acad Sci, Comp & Automat Inst, Budapest, Hungary
[2] Univ Pannonia, Fac Informat Technol, Veszprem, Hungary
[3] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia
[4] Hungarian Acad Sci, Alfred Renyi Inst Math, Budapest, Hungary
[5] Karlsruhe Inst Technol, Karlsruhe, Germany
来源：
GRAPHS AND COMBINATORICS | 2019年 / 35卷 / 05期
基金：
欧洲研究理事会;
关键词：
Dominating set; Total dominating set; Paired-dominating set; Claw-free graph; Cubic graph; NUMBER;
D O I：
10.1007/s00373-019-02063-w
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A paired-dominating set of a graph G is a dominating set D with the additional requirement that the induced subgraph G[D] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two paired-dominating sets.
引用
收藏
页码：1129 / 1138
页数：10
相关论文
共 50 条
  • [21] END SUPER DOMINATING SETS IN GRAPHS
    Akbari, Saieed
    Ghanbari, Nima
    Henning, Michael A.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, : 21 - 47
  • [22] Dominating sets of maximal outerplanar graphs
    Tokunaga, Shin-ichi
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 3097 - 3099
  • [23] Dominating sets for uniform subset graphs
    Bahmani, Abolfazl
    Emami, Mojgan
    Naserian, Ozra
    LINEAR & MULTILINEAR ALGEBRA, 2024, 72 (02) : 283 - 295
  • [24] On Independent Transversal Dominating Sets in Graphs
    Sevilleno, Daven S.
    Jamil, Ferdinand P.
    EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2021, 14 (01): : 149 - 163
  • [25] ON MINIMAL DOMINATING SETS FOR SIGNED GRAPHS
    Ashraf, P. K.
    Germina, K. A.
    ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2015, 15 (02): : 101 - 112
  • [26] On disjoint maximal independent sets in graphs
    Schaudt, Oliver
    INFORMATION PROCESSING LETTERS, 2015, 115 (01) : 23 - 27
  • [27] Some results for the two disjoint connected dominating sets problem
    Liu, Xianliang
    Yang, Zishen
    Wang, Wei
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (06)
  • [28] Explicit construction of mixed dominating sets in generalized Petersen graphs
    Olyaei, Meysam Rajaati Bavil
    Meybodi, Mohsen Alambardar
    Hooshmandasl, Mohammad Reza
    Shakiba, Ali
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (04)
  • [29] Locating-dominating sets: From graphs to oriented graphs
    Bousquet, Nicolas
    Deschamps, Quentin
    Lehtila, Tuomo
    Parreau, Aline
    DISCRETE MATHEMATICS, 2023, 346 (01)
  • [30] Efficient enumeration of dominating sets for sparse graphs
    Kurita, Kazuhiro
    Wasa, Kunihiro
    Arimura, Hiroki
    Uno, Takeaki
    DISCRETE APPLIED MATHEMATICS, 2021, 303 : 283 - 295
12345