Balanced Decomposition of Hypercube

Abstract

A balanced vertex coloring of G is a pair R, B of subsets R , B ïƒVGsuch that RB  ï† and R  B . A subset U of V G is called a balanced set if U induces a connected subgraph with U R  U B . A balanced decomposition of a balanced coloring R, B of G is a partition of vertices   r V G V1 V2 ïŒïƒˆV such that all parts V s i , are balanced sets. The size of the balanced decomposition is defined as the maximum of r V , , V 1 ïŒ . The balanced decomposition number of a graph is the maximum size of the balanced decompositions with R  B  k , where 0 ï‚£ k ï‚£ n 2 . In this paper, some results about balanced decomposition of n -dimensional cube n Q are given.