Locating and paired-dominating sets in graphs

John McCoy, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-206]. A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. We consider paired-dominating sets which are also locating sets, that is distinct vertices of G are dominated by distinct subsets of the paired-dominating set. We consider three variations of sets which are paired-dominating and locating sets and investigate their properties.

Original languageEnglish
Pages (from-to)3268-3280
Number of pages13
JournalDiscrete Applied Mathematics
Issue number15
Publication statusPublished - 6 Aug 2009
Externally publishedYes


  • Differentiating-paired-dominating set
  • Locating-paired-dominating set
  • Metric-locating-paired-dominating set

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Locating and paired-dominating sets in graphs'. Together they form a unique fingerprint.

Cite this