The diameter of paired-domination vertex critical graphs

Michael A. Henning, Christina M. Mynhardt

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199-206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ pr(G - v) < γ pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ pr(G) - 2). For γ pr(G) ≤ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.

Original languageEnglish
Pages (from-to)887-897
Number of pages11
JournalCzechoslovak Mathematical Journal
Issue number4
Publication statusPublished - Dec 2008
Externally publishedYes


  • Bounds
  • Diameter
  • Paired-domination
  • Vertex critical

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'The diameter of paired-domination vertex critical graphs'. Together they form a unique fingerprint.

Cite this