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

dmtcs:1277 - Discrete Mathematics & Theoretical Computer Science, June 2, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.1277
Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graphArticle

Authors: 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.

Comment: 16 pages, 2 figures


Volume: Vol. 18 no. 3
Section: Graph Theory
Published on: June 2, 2016
Imported on: June 2, 2016
Keywords: Mathematics - Combinatorics, 05C76, 05C69

Consultation statistics

This page has been seen 1146 times.
This article's PDF has been downloaded 715 times.