Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647682 | Discrete Mathematics | 2013 | 4 Pages |
Abstract
The concept of balanced decomposition number was introduced by Fujita and Nakamigawa in connection with a simultaneous transfer problem. A balanced colouring of a graph G is a pair (R,B) of disjoint subsets R,BâV(G) with |R|=|B|. A balanced decomposition D of a balanced colouring C=(R,B) of G is a partition of vertices V(G)=V1âªV2âªâ¯âªVr such that G[Vi] is connected and |Viâ©R|=|Viâ©B| for 1â¤iâ¤r. Let C be the set of all balanced colourings of G and D(C) be the set of all balanced decompositions of G for CâC. Then the balanced decomposition number f(G) of G is f(G)=maxCâCminDâD(C)max1â¤iâ¤r|Vi|. Fujita and Nakamigawa conjectured that if G is a 2-vertex connected graph of n vertices, then f(G)â¤ân2â+1. In this paper, we confirm this conjecture in the affirmative.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gerard Jennhwa Chang, N. Narayanan,