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

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2018年 / 48卷 / 27-41期

关键词：

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 条

[21] Cactus graphs with unique minimum dominating sets
Fischermann, M
Volkmann, L
UTILITAS MATHEMATICA, 2003, 63 : 229 - 238
[22] On proper (1,2)-dominating sets in graphs
Michalski, Adrian
Wloch, Iwona
Dettlaff, Magda
Lemanska, Magdalena
MATHEMATICAL METHODS IN THE APPLIED SCIENCES, 2022, 45 (11) : 7050 - 7057
[23] Disjoint Paired-Dominating sets in Cubic Graphs
Bacso, Gabor
Bujtas, Csilla
Tompkins, Casey
Tuza, Zsolt
GRAPHS AND COMBINATORICS, 2019, 35 (05) : 1129 - 1138
[24] DOMINATING SETS OF SOME GRAPHS ASSOCIATED TO COMMUTATIVE RINGS
Mojdeh, D. A.
Rahimi, A. M.
COMMUNICATIONS IN ALGEBRA, 2012, 40 (09) : 3389 - 3396
[25] Number of Dominating Sets in Cylindric Square Grid Graphs
Seungsang Oh
Graphs and Combinatorics, 2021, 37 : 1357 - 1372
[26] Dominating Sets and Induced Matchings in Orthogonal Ray Graphs
Takaoka, Asahi
Tayu, Satoshi
Ueno, Shuichi
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D (12): : 3101 - 3109
[27] Algorithmic results in secure total dominating sets on graphs
Poureidi, Abolfazl
THEORETICAL COMPUTER SCIENCE, 2022, 918 : 1 - 17
[28] Number of Dominating Sets in Cylindric Square Grid Graphs
Oh, Seungsang
GRAPHS AND COMBINATORICS, 2021, 37 (04) : 1357 - 1372
[29] ON MINIMUM INTERSECTIONS OF CERTAIN SECONDARY DOMINATING SETS IN GRAPHS
Kosiorowska, Anna
Michalski, Adrian
Wloch, Iwona
OPUSCULA MATHEMATICA, 2023, 43 (06) : 813 - 827
[30] Disjoint Paired-Dominating sets in Cubic Graphs
Gábor Bacsó
Csilla Bujtás
Casey Tompkins
Zsolt Tuza
Graphs and Combinatorics, 2019, 35 : 1129 - 1138

← 1 2 3 4 5 →