Locating-dominating sets in twin-free graphs

DOI10.1016/J.DAM.2015.06.038zbMATH Open1329.05231arXiv1412.2376OpenAlexW2166937745MaRDI QIDQ906432FDOQ906432

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

Publication date: 21 January 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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)capDeN(v)capD$ 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 $gamm{a}_L(G)$, is the minimum cardinality of a locating-dominating set in $G$. It is conjectured [D. Garijo, A. Gonz'alez and A. M'arquez. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $gamm{a}_L(G)lefracn2$. We prove the general bound $gamm{a}_L(G)lefrac2n3$, slightly improving over the $lfloorfrac2n3floor+1$ bound of Garijo et al. We then provide constructions of graphs reaching the $fracn2$ 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.

Full work available at URL: https://arxiv.org/abs/1412.2376

Recommendations

• Locating-total dominating sets in twin-free graphs: a conjecture
• Domination and location in twin-free digraphs
• Locating and paired-dominating sets in graphs
• Locating-dominating sets in hypergraphs
• Problems related to a conjecture on location-domination in twin-free graphs
• On locating-domination in graphs
• Locating-total domination in graphs
• scientific article; zbMATH DE number 861343
• On locating-dominating set of regular graphs
• Locating-dominating sets: from graphs to oriented graphs

zbMATH Keywords

dominating setslocating-dominating sets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Domination-balanced graphs
• Nordhaus-Gaddum bounds for locating domination
• Title not available (Why is that?)
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Extremal graphs for the identifying code problem
• The difference between the metric dimension and the determining number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Domination and location in acyclic graphs
• Title not available (Why is that?)
• Locating-total domination in claw-free cubic graphs
• Title not available (Why is that?)

Cited In (25)

• My favorite domination conjectures in graph theory are bounded
• Revisiting and improving upper bounds for identifying codes
• Locating-dominating sets in local tournaments
• \( [ 1 , 2 ]\)-dimension of graphs
• Bounds and extremal graphs for total dominating identifying codes
• Extremal cubic graphs for fault-tolerant locating domination
• Progress towards the two-thirds conjecture on locating-total dominating sets
• Locating domination in bipartite graphs and their complements
• Locating-total dominating sets in twin-free graphs: a conjecture
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• On connected 3-\(\gamma_L\)-dot-critical graphs
• Location-domination in line graphs
• Characterizing extremal graphs for open neighbourhood location-domination
• Location-domination and matching in cubic graphs
• Domination and location in twin-free digraphs
• A note on locating-dominating sets in twin-free graphs
• Locating-dominating sets of functigraphs
• An extension of locating-total domination problem and its complexity
• Bounds on the locating Roman domination number in trees
• On redundant locating-dominating sets
• Bounds on the locating-domination number and differentiating-total domination number in trees
• Optimal error-detection system for identifying codes
• Problems related to a conjecture on location-domination in twin-free graphs
• On locating-dominating set of regular graphs
• Locating-dominating sets: from graphs to oriented graphs

This page was built for publication: Locating-dominating sets in twin-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906432)