Paired Domination Problems of Infinite Diamond Lattice

Abstract

A set $S$ of vertices of a graph $G(V,E)$ is a $dominatingset$ if every vertex of $V\setminus S$ is adjacent to some vertex in $S$. A dominating set is said to be $efficient$ if every vertex of $V\setminus S$ is dominated by exactly one vertex of $S$. A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. A set $S$ of vertices in $G$ is a total dominating set of $G$ if every vertex of $V$ is adjacent to some vertex in $S$. In this paper, we construct a minimum paired dominating set and a minimum total dominating set for the infinite diamond lattice. The total domatic number of $G$ is the size of a maximum cardinality partition of $V$ into total dominating sets. We also demonstrate that the total domatic number of the infinite diamond lattice is 4.