Location-domination and matching in cubic graphs

Abstract

A dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex outside $D$ is adjacent to a vertex in $D$. A locating-dominating set of $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)\cap D\ne N(v)\cap 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 ${\gamma }_L(G)$, is the minimum cardinality of a locating-dominating set in $G$. Garijo, Gonzalez and Marquez [Applied Math. Computation 249 (2014), 487--501] posed the conjecture that for $n$ sufficiently large, the maximum value of the location-domination number of a twin-free, connected graph on $n$ vertices is equal to $\lfloor \frac{n}{2}\rfloor$. We propose the related (stronger) conjecture that if $G$ is a twin-free graph of order $n$ without isolated vertices, then ${\gamma }_L(G)\le \frac{n}{2}$. We prove the conjecture for cubic graphs. We rely heavily on proof techniques from matching theory to prove our result.

16 pages; 4 figures

References in corpus (3)

• Locating-dominating sets in twin-free graphs
• Extremal graphs for the identifying code problem
• Resolving sets for breaking symmetries of graphs

Cited by in corpus (4)

• Location-domination in line graphs
• Domination and location in twin-free digraphs
• Locating-dominating partitions for some classes of graphs
• Progress towards the two-thirds conjecture on locating-total dominating sets