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 条
  • [31] Block graphs with unique minimum dominating sets
    Fischermann, M
    DISCRETE MATHEMATICS, 2001, 240 (1-3) : 247 - 251
  • [32] Independent dominating sets in graphs of girth five
    Harutyunyan, Ararat
    Horn, Paul
    Verstraete, Jacques
    COMBINATORICS PROBABILITY & COMPUTING, 2021, 30 (03) : 344 - 359
  • [33] On the Number of -Dominating Independent Sets in Planar Graphs
    Taletskii D.S.
    Journal of Applied and Industrial Mathematics, 2024, 18 (01) : 167 - 178
  • [34] Strength of strongest dominating sets in fuzzy graphs
    Jalalvand, Marzieh Farhadi
    Rad, Nader Jafari
    Ghorani, Maryam
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2021, 6 (02) : 287 - 297
  • [35] Efficient enumeration of dominating sets for sparse graphs
    Kurita, Kazuhiro
    Wasa, Kunihiro
    Arimura, Hiroki
    Uno, Takeaki
    DISCRETE APPLIED MATHEMATICS, 2021, 303 : 283 - 295
  • [36] Counting dominating sets and related structures in graphs
    Cutler, Jonathan
    Radcliffe, A. J.
    DISCRETE MATHEMATICS, 2016, 339 (05) : 1593 - 1599
  • [37] Disconnected character graphs and odd dominating sets
    Ebrahimi, Mahdi
    COMMUNICATIONS IN ALGEBRA, 2021, 49 (08) : 3310 - 3314
  • [38] On dominating sets of maximal outerplanar and planar graphs
    Li, Zepeng
    Zhu, Enqiang
    Shao, Zehui
    Xu, Jin
    DISCRETE APPLIED MATHEMATICS, 2016, 198 : 164 - 169
  • [39] Minimal dominating sets in interval graphs and trees
    Golovach, Petr A.
    Heggernes, Pinar
    Kante, Mamadou Moustapha
    Kratsch, Dieter
    Villanger, Yngve
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 162 - 170
  • [40] Cactus graphs with unique minimum dominating sets
    Fischermann, M
    Volkmann, L
    UTILITAS MATHEMATICA, 2003, 63 : 229 - 238
12345