Header menu link for other important links
X
On a conjecture on the balanced decomposition number
Gerard Jennhwa Chang,
Published in Elsevier BV
2013
Volume: 313
   
Issue: 14
Pages: 1511 - 1514
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,BEV(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.
About the journal
PublisherData powered by TypesetElsevier BV
ISSN0012365X
Open AccessNo