Locating-dominating sets: from graphs to oriented graphs

DOI10.1016/J.DISC.2022.113124MaRDI QIDQ2092344zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä, Aline Parreau

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

locating-dominating setlocation-dominationoriented graph

Mathematics Subject Classification ID

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

Abstract: A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,votinS$, we have $N(u)capSeN(v)capS$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $winV$, $N[w{]}^{-}capS=emptyset$ and for each pair of vertices $u,vinVsetminusS$, $N^{-}(u)capSe{N}^{-}(v)capS$. We consider the following two parameters. Given an undirected graph $G$, we look for $oversetightarrow{gamma}_{LD}(G)$ ($oversetightarrow{Gamma}_{LD}(G))$ which is the size of the smallest (largest) optimal locating-dominating set over all orientations of $G$. In particular, if $D$ is an orientation of $G$, then $oversetightarrow{gamma}_{LD}(G)leq{gamma}_{LD}(D)leqoversetightarrow{Gamma}_{LD}(G)$. For the best orientation, we prove that, for every twin-free graph $G$ on $n$ vertices, $oversetightarrow{gamma}_{LD}(G)len/2$ proving a ``directed version of a conjecture on $gamm{a}_{LD}(G)$. Moreover, we give some bounds for $oversetightarrow{gamma}_{LD}(G)$ on many graph classes and drastically improve the value $n/2$ for (almost) $d$-regular graphs by showing that $oversetightarrow{gamma}_{LD}(G)inO(logd/dcdotn)$ using a probabilistic argument. While $oversetightarrow{gamma}_{LD}(G)leqgamm{a}_{LD}(G)$ holds for every graph $G$, we give some graph classes graphs for which $oversetightarrow{Gamma}_{LD}(G)geq{gamma}_{LD}(G)$ and some for which $oversetightarrow{Gamma}_{LD}(G)leq{gamma}_{LD}(G)$. We also give general bounds for $oversetightarrow{Gamma}_{LD}(G)$. Finally, we show that for many graph classes $oversetightarrow{Gamma}_{LD}(G)$ is polynomial on $n$ but we leave open the question whether there exist graphs with $oversetightarrow{Gamma}_{LD}(G)inO(logn)$.

Recommendations

• On locating-domination in graphs
• On locating-dominating set of regular graphs
• Locating-dominating sets in hypergraphs
• A polyhedral approach to locating-dominating sets in graphs
• Locating-total domination in graphs
• Locating-dominating sets of functigraphs
• Locating and paired-dominating sets in graphs
• scientific article; zbMATH DE number 861343
• scientific article; zbMATH DE number 637310
• A note on the locating-total domination in graphs

Cites work

• An induced subgraph characterization of domination perfect graphs
• Claw-free graphs. VI: Colouring
• Codes identifying sets of vertices in random networks
• Directed domination in oriented graphs
• Domination and location in acyclic graphs
• Domination and location in twin-free digraphs
• Fault-tolerant locating-dominating sets
• Graph theory with applications
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• scientific article; zbMATH DE number 5919758 (Why is no real title available?)
• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (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 4183452 (Why is no real title available?)
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Locating-dominating sets in twin-free graphs
• Locating-domination and identifying codes in trees
• Metric dimension: from graphs to oriented graphs
• On a Problem in Graph Theory
• On the degrees of the vertices of a directed graph
• On the minimum size of an identifying code over all orientations of a graph
• Path factors in claw-free graphs
• The difference between the metric dimension and the determining number of a graph
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Vizing bound for the chromatic number on some graph classes

Cited in

(12)

• On locating-dominating set of regular graphs
• Locating-dominating sets of functigraphs
• Revisiting and improving upper bounds for identifying codes
• On finding the best and worst orientations for the metric dimension
• The localization game on oriented graphs
• Locating-dominating sets in local tournaments
• Extremal Digraphs for open neighbourhood location-domination and identifying codes
• A note on locating-dominating sets in twin-free graphs
• On identifying vertices of tournament digraphs
• Independent location-domination number of graphs
• Domination and location in twin-free digraphs
• Locating-dominating sets in twin-free graphs

This page was built for publication: Locating-dominating sets: from graphs to oriented graphs

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