In graph theory, a paired dominating set of a graph G = ( V , E ) {\displaystyle G=(V,E)} is a dominating set S {\displaystyle S} of vertices such that the induced subgraph G [ S ] {\displaystyle G[S]} contains at least one perfect matching. The concept was introduced by Teresa W. Haynes and Peter J. Slater in 1998. The paired domination number, denoted γ p ( G ) {\displaystyle \gamma _{p}(G)} , is the minimum cardinality of a paired dominating set of G {\displaystyle G} . The concept models a situation in which guards are placed at vertices of a graph to dominate (protect) all vertices, with the additional constraint that each guard is assigned another adjacent guard as a backup. This is equivalent to finding a set M {\displaystyle M} of independent edges (a matching) whose endpoints form a dominating set.
Properties and bounds Since every paired dominating set is a dominating set, and every dominating set whose induced subgraph has a perfect matching is necessarily a total dominating set, the following chain of inequalities holds for any graph G {\displaystyle G} without isolated vertices:
γ ( G ) ≤ γ t ( G ) ≤ γ p ( G ) {\displaystyle \gamma (G)\leq \gamma _{t}(G)\leq \gamma _{p}(G)}
where γ ( G ) {\displaystyle \gamma (G)} is the domination number and γ t ( G ) {\displaystyle \gamma _{t}(G)} is the total domination number. Haynes and Slater characterized the triples ( a , b , c ) {\displaystyle (a,b,c)} of positive integers with a ≤ b ≤ c {\displaystyle a\leq b\leq c} for which there exists a graph G {\displaystyle G} satisfying γ ( G ) = a {\displaystyle \gamma (G)=a} , γ t ( G ) = b {\displaystyle \gamma _{t}(G)=b} , and γ p ( G ) = c {\displaystyle \gamma _{p}(G)=c} . Because the endpoints of any maximal matching form a paired dominating set, the paired domination number is bounded above by twice the size of any maximal matching of the graph:
γ p ( G ) ≤ 2 ν ( G ) {\displaystyle \gamma _{p}(G)\leq 2\,\nu (G)}
… excerpt ends here. Continue reading the full article.
