### 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.

#### Keywords

Balanced decomposition, vertex partition

DOI

10.12783/dtcse/aiea2017/14931

10.12783/dtcse/aiea2017/14931

### Refbacks

- There are currently no refbacks.