Location-domination and matching in cubic graphs

A dominating set of a graph GG is a set DD of vertices of GG such that every vertex outside DD is adjacent to a vertex in DD. A locating-dominating set of GG is a dominating set DD of GG with the additional property that every two distinct vertices outside DD have distinct neighbors in DD; that is, for distinct vertices uu and vv outside DD, N(u)∩D≠N(v)∩DN(u)∩D≠N(v)∩D where N(u)N(u) denotes the open neighborhood of uu. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of GG, denoted γL(G)γL(G), is the minimum cardinality of a locating-dominating set in GG. Garijo et al. (2014) posed the conjecture that for nn sufficiently large, the maximum value of the location-domination number of a twin-free, connected graph on nn vertices is equal to  ⌊n2⌋. We propose the related (stronger) conjecture that if GG is a twin-free graph of order nn without isolated vertices, then γL(G)≤n2. We prove the conjecture for cubic graphs. We rely heavily on proof techniques from matching theory to prove our result.