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 条
  • [1] Disjoint Paired-Dominating sets in Cubic Graphs
    Gábor Bacsó
    Csilla Bujtás
    Casey Tompkins
    Zsolt Tuza
    Graphs and Combinatorics, 2019, 35 : 1129 - 1138
  • [2] Graphs with disjoint dominating and paired-dominating sets
    Southey, Justin
    Henning, Michael A.
    CENTRAL EUROPEAN JOURNAL OF MATHEMATICS, 2010, 8 (03): : 459 - 467
  • [3] Graphs with unique minimum paired-dominating set
    Chen, Lei
    Lu, Changhong
    Zeng, Zhenbing
    ARS COMBINATORIA, 2015, 119 : 177 - 192
  • [4] ACYCLIC TOTAL DOMINATING SETS IN CUBIC GRAPHS
    Goddard, Wayne
    Henning, Michael A.
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2019, 13 (01) : 73 - 84
  • [5] γ-PAIRED DOMINATING GRAPHS OF CYCLES
    Eakawinrujee, Pannawat
    Trakultraipruk, Nantapath
    OPUSCULA MATHEMATICA, 2022, 42 (01) : 31 - 54
  • [6] γ-Paired Dominating Graphs of Paths
    Eakawinrujee, Pannawat
    Trakultraipruk, Nantapath
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2022, 17 (02): : 739 - 752
  • [7] Dominating Sets and Connected Dominating Sets in Dynamic Graphs
    Hjuler, Niklas
    Italiano, Giuseppe F.
    Parotsidis, Nikos
    Saulpic, David
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [8] Dominating and total dominating partitions in cubic graphs
    Southey, Justin
    Henning, Michael A.
    CENTRAL EUROPEAN JOURNAL OF MATHEMATICS, 2011, 9 (03): : 699 - 708
  • [9] Graphs with few total dominating sets
    Krzywkowski, Marcin
    Wagner, Stephan
    DISCRETE MATHEMATICS, 2018, 341 (04) : 997 - 1009
  • [10] On disjoint matchings in cubic graphs
    Mkrtchyan, Vahan V.
    Petrosyan, Samvel S.
    Vardanyan, Gagik N.
    DISCRETE MATHEMATICS, 2010, 310 (10-11) : 1588 - 1613
12345