Article ID Journal Published Year Pages File Type
420723 Discrete Applied Mathematics 2009 9 Pages PDF
Abstract

The question of whether a graph can be partitioned into kk independent dominating sets, which is the same as having a fall  kk-colouring  , is considered. For k=3k=3, it is shown that a graph GG can be partitioned into three independent dominating sets if and only if the cartesian product G□K2G□K2 can be partitioned into three independent dominating sets. The graph K2K2 can be replaced by any graph HH such that there is a mapping f:Qn→Hf:Qn→H, where ff is a type-II graph homomorphism.The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of kk, iterated cartesian products are considered, leading to a result that shows for what values of kk the hypercubes can be partitioned into kk independent dominating sets.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,