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 条
  • [41] Metric-locating-dominating sets in graphs
    Henning, MA
    Oellermann, OR
    [J]. ARS COMBINATORIA, 2004, 73 : 129 - 141
  • [42] Fixed Set Search Applied to the Maximum Disjoint Dominating Sets Problem
    Jovanovic, Raka
    Voss, Stefan
    [J]. METAHEURISTICS, MIC 2024, PT II, 2024, 14754 : 347 - 353
  • [43] Dominating Sets and Induced Matchings in Orthogonal Ray Graphs
    Takaoka, Asahi
    Tayu, Satoshi
    Ueno, Shuichi
    [J]. IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D (12): : 3101 - 3109
  • [44] Number of Dominating Sets in Cylindric Square Grid Graphs
    Seungsang Oh
    [J]. Graphs and Combinatorics, 2021, 37 : 1357 - 1372
  • [45] DOMINATING SETS OF SOME GRAPHS ASSOCIATED TO COMMUTATIVE RINGS
    Mojdeh, D. A.
    Rahimi, A. M.
    [J]. COMMUNICATIONS IN ALGEBRA, 2012, 40 (09) : 3389 - 3396
  • [46] ON MINIMUM INTERSECTIONS OF CERTAIN SECONDARY DOMINATING SETS IN GRAPHS
    Kosiorowska, Anna
    Michalski, Adrian
    Wloch, Iwona
    [J]. OPUSCULA MATHEMATICA, 2023, 43 (06) : 813 - 827
  • [47] Tropical dominating sets in vertex-coloured graphs
    d'Auriac, J. -A. Angles
    Bujtas, Cs.
    El Maftouhi, A.
    Karpinski, M.
    Manoussakis, Y.
    Montero, L.
    Narayanan, N.
    Rosaz, L.
    Thapper, J.
    Tuza, Zs.
    [J]. JOURNAL OF DISCRETE ALGORITHMS, 2018, 48 (27-41) : 27 - 41
  • [48] Number of Dominating Sets in Cylindric Square Grid Graphs
    Oh, Seungsang
    [J]. GRAPHS AND COMBINATORICS, 2021, 37 (04) : 1357 - 1372
  • [49] DOMINATING SETS AND DOMINATION POLYNOMIALS OF CERTAIN GRAPHS, II
    Alikhani, Saeid
    Peng, Yee-hock
    [J]. OPUSCULA MATHEMATICA, 2010, 30 (01) : 37 - 51
  • [50] CLIQUE-TRANSVERSAL SETS IN LINE GRAPHS OF CUBIC GRAPHS AND TRIANGLE-FREE GRAPHS
    Kang, Liying
    Shan, Erfang
    [J]. BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2015, 52 (05) : 1423 - 1431
12345