The balanced decomposition number and vertx connectivity

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.
Original languageUnknown
Pages (from-to)1597-1616
JournalSiam Journal On Discrete Mathematics
Issue number4
Publication statusPublished - 1 Jan 2010

Cite this