A1 Refereed original research article in a scientific journal
Progress towards the two-thirds conjecture on locating-total dominating sets
Authors: Chakraborty, Dipayan; Foucaud, Florent; Hakanen, Anni; Henning, Michael A.; Wagler, Annegret K.
Publisher: Elsevier
Publication year: 2024
Journal: Discrete Mathematics
Journal name in source: Discrete Mathematics
Article number: 114176
Volume: 347
Issue: 12
ISSN: 0012-365X
eISSN: 1872-681X
DOI: https://doi.org/10.1016/j.disc.2024.114176
Web address : https://doi.org/10.1016/j.disc.2024.114176
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/457313437
Preprint address: https://arxiv.org/abs/2211.14178
Abstract
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 S have distinct neighborhoods within S. The smallest size of such a set is denoted by γtL(G). It has been conjectured that γ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.
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 S have distinct neighborhoods within S. The smallest size of such a set is denoted by γtL(G). It has been conjectured that γ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.
UTU Research Portal