Locating-dominating sets in twin-free graphs

DOI10.1016/J.DAM.2015.06.038MaRDI QIDQ906432zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

dominating setslocating-dominating sets

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 4053685 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 4103125 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 861343 (Why is no real title available?)
• Domination and location in acyclic graphs
• Domination-balanced graphs
• Extremal graphs for the identifying code problem
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Locating-total domination in claw-free cubic graphs
• Nordhaus-Gaddum bounds for locating domination
• The difference between the metric dimension and the determining number of a graph

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
• Locating domination in bipartite graphs and their complements
• Progress towards the two-thirds conjecture on locating-total dominating sets
• 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
• Locating-dominating sets of functigraphs
• A note on locating-dominating sets in twin-free graphs
• Bounds on the locating Roman domination number in trees
• An extension of locating-total domination problem and its complexity
• Bounds on the locating-domination number and differentiating-total domination number in trees
• On redundant locating-dominating sets
• 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)