Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph

Tadeja Kraner Šumenjak; Iztok Peterin; Douglas F. Rall; Aleksandra Tepeh

doi:10.46298/dmtcs.1277

paper

Partitioning the vertex set of $G$ to make $G □ H$ an efficient open domination graph

arXiv:1508.04029 · doi:10.46298/dmtcs.1277

Abstract

A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs $G$ for which the Cartesian product $G □ H$ is an efficient open domination graph when $H$ is a complete graph of order at least 3 or a complete bipartite graph. The characterization is based on the existence of a certain type of weak partition of $V (G)$ . For the class of trees when $H$ is complete of order at least 3, the characterization is constructive. In addition, a special type of efficient open domination graph is characterized among Cartesian products $G □ H$ when $H$ is a 5-cycle or a 4-cycle.

arXiv comment16 pages, 2 figures

Partitioning the vertex set of G to make G□H an efficient open domination graph

Abstract

References in corpus (2)

Partitioning the vertex set of $G$ to make $G □ H$ an efficient open domination graph