Graphs with small balanced decomposition numbers

機構典藏 > College of Sciences > Department of Applied Mathematics and Data Science > Journal Article > Item 987654321/115405

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/115405

Title:	Graphs with small balanced decomposition numbers
Authors:	Hsiang-Chun Hsu;Gerard Jennhwa Chang
Keywords:	Balanced coloring;Balanced decomposition;Balanced decomposition number;Connectivity
Date:	2014-08-31
Issue Date:	2018-10-25 12:10:56 (UTC+8)
Publisher:	Springer US
Abstract:	A balanced coloring of a graph G is an ordered pair (R,B) of disjoint subsets R,B⊆V(G) with \|R\|=\|B\| . The balanced decomposition number f(G) of a connected graph G is the minimum integer f such that for any balanced coloring (R,B) of G there is a partition P of V(G) such that S induces a connected subgraph with \|S\|≤f and \|S∩R\|=\|S∩B\| for S∈P . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph G of n vertices has f(G)=3 if and only if G is ⌊n2⌋ -connected but is not a complete graph.
Relation:	Journal of Combinatorial Optimization 28(2), p.505-510
DOI:	10.1007/s10878-012-9576-6
Appears in Collections:	[Department of Applied Mathematics and Data Science] Journal Article

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	141	View/Open