Tropical dominating sets in vertex-coloured graphs

被引:1
作者
d'Auriac, J. -A. Angles [1 ]
Bujtas, Cs. [2 ]
El Maftouhi, A. [1 ]
Karpinski, M. [3 ]
Manoussakis, Y. [1 ]
Montero, L. [1 ]
Narayanan, N. [1 ]
Rosaz, L. [1 ]
Thapper, J. [4 ]
Tuza, Zs. [2 ,5 ]
机构
[1] Univ Paris Sud, LRI, Bat 650, F-91405 Orsay, France
[2] Univ Pannonia, Dept Comp Sci & Syst Technol, Egyet U 10, H-8200 Veszprem, Hungary
[3] Univ Bonn, Dept Comp Sci, Friedrich Ebert Allee 144, D-53113 Bonn, Germany
[4] Univ Paris Est, LIGM, Bat Copern,5 Bd Descartes, F-77454 Marne La Vallee 2, France
[5] Hungarian Acad Sci, Alfred Renyi Inst Math, Realtanoda U 13-15, H-1053 Budapest, Hungary
关键词
Dominating set; Vertex-coloured graph; Approximation; Random graphs;
D O I
10.1016/j.jda.2018.03.001
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give an optimal upper bound for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:27 / 41
页数:15
相关论文
共 50 条
  • [31] DOMINATING SETS AND DOMINATION POLYNOMIALS OF CERTAIN GRAPHS, II
    Alikhani, Saeid
    Peng, Yee-hock
    [J]. OPUSCULA MATHEMATICA, 2010, 30 (01) : 37 - 51
  • [32] Metric-locating-dominating sets of graphs for constructing related subsets of vertices
    Gonzalez, Antonio
    Hernando, Carmen
    Mora, Merce
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2018, 332 : 449 - 456
  • [33] Dominating Sets in Two-Directional Orthogonal Ray Graphs
    Takaoka, Asahi
    Tayu, Satoshi
    Ueno, Shuichi
    [J]. IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2015, E98D (08): : 1592 - 1595
  • [34] Locating and differentiating-total dominating sets in unicyclic graphs
    Ning, Wenjie
    Lu, Mei
    Guo, Jia
    [J]. ARS COMBINATORIA, 2017, 132 : 241 - 255
  • [35] Explicit construction of mixed dominating sets in generalized Petersen graphs
    Olyaei, Meysam Rajaati Bavil
    Meybodi, Mohsen Alambardar
    Hooshmandasl, Mohammad Reza
    Shakiba, Ali
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (04)
  • [36] Multiple Intruder Locating Dominating Sets in Graphs: An Algorithmic Approach
    Venugopal, K.
    Vidya, K. A.
    [J]. COMMUNICATIONS IN MATHEMATICS AND APPLICATIONS, 2020, 11 (02): : 259 - 269
  • [37] Distributed Connected Dominating Sets in Unit Square and Disk Graphs
    Gorain, Barun
    Mondal, Kaushik
    Pandit, Supantha
    [J]. THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022, 2022, 13571 : 346 - 358
  • [38] Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes
    Czyzowicz, J.
    Dobrev, S.
    Fevens, T.
    Gonzalez-Aguilar, H.
    Kranakis, E.
    Opatrny, J.
    Urrutia, J.
    [J]. LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 : 158 - +
  • [39] On distance r-dominating and 2r-independent sets in sparse graphs
    Dvorak, Zdenek
    [J]. JOURNAL OF GRAPH THEORY, 2019, 91 (02) : 162 - 173
  • [40] Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets
    Cui, Qing
    [J]. GRAPHS AND COMBINATORICS, 2020, 36 (06) : 1723 - 1740