Metric-locating-dominating sets in graphs

Michael A. Henning, Ortrud R. Oellermann

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)

Abstract

If u and v are vertices of a graph, then d(u, v) denotes the distance from u to v. Let S = {v1, v2, ... ,vk} be a set of vertices in a connected graph G. For each v ∈ V(G), the k-vector cs(v) is defined by cS(v) = (d(v, v1), d(v, v2), ⋯, d(v, vk)). A dominating set S = {v1, v 2, ... , vk} in a connected graph G is a metric-locating-dominating set, or an MLD-set, if the k-vectors cS(v) for v ∈ V(G) are distinct. The metric-location-domination number γM(G) of G is the minimum cardinality of an MLD-set in G. We determine the metric-location-domination number of a tree in terms of its domination number. In particular, we show that γ(T) = γM(T) if and only if T contains no vertex that is adjacent to two or more end-vertices. We show that for a tree T the ratio γL(T)/γM(T) is bounded above by 2, where γL(G) is the location- domination number defined by Slater (Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445-455). We establish that if G is a connected graph of order n ≥ 2, then γM(T) = n - 1 if and only if G = K1,n-1 or G = Kn. The connected graphs G of order n ≥ 4 for which γM (T) = n - 2 are characterized in terms of seven families of graphs.

Original languageEnglish
Pages (from-to)129-141
Number of pages13
JournalArs Combinatoria
Volume73
Publication statusPublished - Oct 2004
Externally publishedYes

Keywords

  • Dominating set
  • Locating set
  • Metric-locating-dominating set

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Metric-locating-dominating sets in graphs'. Together they form a unique fingerprint.

Cite this