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 条

[41] Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets [J].

Qing Cui .

Graphs and Combinatorics, 2020, 36 :1723-1740

[42] H-GAMES PLAYED ON VERTEX SETS OF RANDOM GRAPHS [J].

Kronenberg, Gal ;

Mond, Adva ;

Naor, Alon .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (02) :864-916

[43] What Can Be Approximated Locally? Case Study: Dominating Sets in Planar Graphs [J].

Lenzen, Christoph ;

Oswald, Yvonne Anne ;

Wattenhofer, Roger .

SPAA'08: PROCEEDINGS OF THE TWENTIETH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2008, :46-54

[44] Finding Hidden Hubs and Dominating Sets in Sparse Graphs by Randomized Neighborhood Queries [J].

Damaschke, Peter .

NETWORKS, 2011, 57 (04) :344-350

[45] Price of Connectivity for the Vertex Cover Problem and the Dominating Set Problem: Conjectures and Investigation of Critical Graphs [J].

Camby, Eglantine .

GRAPHS AND COMBINATORICS, 2019, 35 (01) :103-118

[46] Price of Connectivity for the Vertex Cover Problem and the Dominating Set Problem: Conjectures and Investigation of Critical Graphs [J].

Eglantine Camby .

Graphs and Combinatorics, 2019, 35 :103-118

[47] Reconfiguration of dominating sets [J].

Suzuki, Akira ;

Mouawad, Amer E. ;

Nishimura, Naomi .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (04) :1182-1195

[48] Dominating sets of centipedes [J].

Alikhani, Saeid ;

Peng, Yee-Hock .

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2009, 12 (04) :411-428

[49] Reconfiguration of dominating sets [J].

Akira Suzuki ;

Amer E. Mouawad ;

Naomi Nishimura .

Journal of Combinatorial Optimization, 2016, 32 :1182-1195

[50] DOMINATING VERTEX COVERS: THE VERTEX-EDGE DOMINATION PROBLEM [J].

Klostermeyer, William F. ;

Messinger, Margaret Ellen ;

Yeo, Anders .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (01) :123-132

← 1 2 3 4 5 →