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 条

[1] 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,
[2] Super Dominating Sets in Graphs
M. Lemańska
V. Swaminathan
Y. B. Venkatakrishnan
R. Zuazua
Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2015, 85 : 353 - 357
[3] Super Dominating Sets in Graphs
Lemanska, M.
Swaminathan, V.
Venkatakrishnan, Y. B.
Zuazua, R.
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES INDIA SECTION A-PHYSICAL SCIENCES, 2015, 85 (03) : 353 - 357
[4] On the number of independent and k-dominating sets in graphs with average vertex degree at most k
Taletskii, D. S.
SBORNIK MATHEMATICS, 2023, 214 (11) : 1627 - 1650
[5] Dominating sets for uniform subset graphs
Bahmani, Abolfazl
Emami, Mojgan
Naserian, Ozra
LINEAR & MULTILINEAR ALGEBRA, 2024, 72 (02): : 283 - 295
[6] Dominating sets of maximal outerplanar graphs
Tokunaga, Shin-ichi
DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 3097 - 3099
[7] On dominating sets of maximal outerplanar graphs
Campos, C. N.
Wakabayashi, Y.
DISCRETE APPLIED MATHEMATICS, 2013, 161 (03) : 330 - 335
[8] EQUITABLE RESOLVING DOMINATING SETS IN GRAPHS
Vaidya, S. K.
Kelaiya, J. B.
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2023, 38 : 15 - 28
[9] Algebraic Structures on Dominating Sets of Graphs
Swain, Srinibas
INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2012, 12 (11): : 23 - 24
[10] ON MINIMAL DOMINATING SETS FOR SIGNED GRAPHS
Ashraf, P. K.
Germina, K. A.
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2015, 15 (02): : 101 - 112

← 1 2 3 4 5 →