Locating-dominating sets in twin-free graphs

Florent Foucaud, Michael A. Henning, Christian Löwenstein, Thomas Sasse

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)

Abstract

A locating-dominating set of a graph G is a dominating set D of G with the additional property that every two distinct vertices outside D have distinct neighbors in D; that is, for distinct vertices u and v outside D, N(u)∩D≠N(v)∩D where N(u) denotes the open neighborhood of u. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of G, denoted γL(G), is the minimum cardinality of a locating-dominating set in G. It is conjectured by Garijo et al. (2014) that if G is a twin-free graph of order n without isolated vertices, then γL(G)≤n2. We prove the general bound γL(G)≤2n3, slightly improving over the ⌊2n3⌋+1 bound of Garijo et al. We then provide constructions of graphs reaching the n2 bound, showing that if the conjecture is true, the family of extremal graphs is a very rich one. Moreover, we characterize the trees G that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.

Original languageEnglish
Pages (from-to)52-58
Number of pages7
JournalDiscrete Applied Mathematics
Volume200
DOIs
Publication statusPublished - 19 Feb 2016

Keywords

  • Dominating sets
  • Locating-dominating sets

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Locating-dominating sets in twin-free graphs'. Together they form a unique fingerprint.

Cite this