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

Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael A. Henning, Annegret K. Wagler

Research output: Contribution to journalArticlepeer-review

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)≤[Formula presented] 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.

Original languageEnglish
Article number114176
JournalDiscrete Mathematics
Volume347
Issue number12
DOIs
Publication statusPublished - Dec 2024

Keywords

  • Block graph
  • Cobipartite graph
  • Locating-total dominating sets
  • Split graph
  • Subcubic graph
  • Total dominating set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Progress towards the two-thirds conjecture on locating-total dominating sets'. Together they form a unique fingerprint.

Cite this