Tadeja Kraner Šumenjak ; Iztok Peterin ; Douglas F. Rall ; Aleksandra Tepeh
-
Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient
open domination graph
Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient
open domination graph
Authors: Tadeja Kraner Šumenjak ; Iztok Peterin ; Douglas F. Rall ; Aleksandra Tepeh
NULL##NULL##NULL##NULL
Tadeja Kraner Šumenjak;Iztok Peterin;Douglas F. Rall;Aleksandra Tepeh
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 \Box 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 \Box H$ when $H$ is a 5-cycle or a 4-cycle.