Graphs with large paired-domination number

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 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 , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.