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) c a p D e q N (v) c a p 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

g a m m a_{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

l f l o o r f r a c n 2 f l o o r

. We propose the related (stronger) conjecture that if

G

is a twin-free graph of order

n

without isolated vertices, then

g a m m a_{L} (G) l e q f r a c n 2

. We prove the conjecture for cubic graphs. We rely heavily on proof techniques from matching theory to prove our result.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Location-domination and matching in cubic graphs