The balanced decomposition number and vertx connectivity

The balanced decomposition number f(G) of a graph G was introduced by Fujita and Nakamigawa [Discr. Appl. Math., 156 (2008), pp. 3339-3344]. A balanced coloring of a graph G is a coloring of some of the vertices of G with two colors, such that there is the same number of vertices in each color. Then, f(G) is the minimum integer s with the following property: For any balanced coloring of G, there is a partition V (G) = V-1 (boolean OR) over dot...(boolean OR) over dot V-r such that, for every i, Vi induces a connected subgraph, vertical bar V-i vertical bar <= s, and V-i contains the same number of colored vertices in each color. Fujita and Nakamigawa studied the function f(G) for many basic families of graphs, and demonstrated some applications. In this paper, we shall continue the study of the function f(G). We give a characterization for noncomplete graphs G of order n which are [n/2]-connected, in view of the balanced decomposition number. We shall prove that a necessary and sufficient condition for such [n/2]-connected graphs G is f(G) = 3. We shall also determine f(G) when G is a complete multipartite graph, and when G is a generalized circle minus-graph (i.e., a graph which is a subdivision of a multiple edge). Some applications will also be discussed. Further results about the balanced decomposition number also appear in two subsequent papers by Fujita and Liu.