Progress towards the two-thirds conjecture on locating-total dominating sets

被引：0

作者：

Chakraborty, Dipayan ^{[1
,3
]}

Foucaud, Florent ^{[1
]}

Hakanen, Anni ^{[1
,2
]}

Henning, Michael A. ^{[3
]}

Wagler, Annegret K. ^{[1
]}

机构：

[1] Univ Clermont Auvergne, LIMOS, Mines St Etienne, CNRS,Clermont Auvergne INP, F-63000 Clermont Ferrand, France

[2] Univ Turku, Dept Math & Stat, Turku, Finland

[3] Univ Johannesburg, Dept Math & Appl Math, Johannesburg, South Africa

来源：

DISCRETE MATHEMATICS | 2024年 / 347卷 / 12期

基金：

新加坡国家研究基金会; 芬兰科学院;

关键词：

Locating-total dominating sets; Total dominating set; Subcubic graph; Split graph; Block graph; Cobipartite graph; COMPLEXITY; GRAPHS; CODES;

D O I：

10.1016/j.disc.2024.114176

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study upper bounds on the size of optimum locating-total dominating sets in graphs. A set S of vertices of a graph G is a locating-total dominating set if every vertex of G has a neighbor in S, and if any two vertices outside Shave distinct neighborhoods within S. The smallest size of such a set is denoted by gamma tL(G). It has been conjectured that gamma tL(G) <= 2n3 holds for every twin-free graph G of order n without isolated vertices. We prove that the conjecture holds for cobipartite graphs, split graphs, block graphs and subcubic graphs. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

引用

页数：14