Graphs with small balanced decomposition numbers
學年 103
學期 1
出版(發表)日期 2014-08-31
作品名稱 Graphs with small balanced decomposition numbers
作品名稱(其他語言)
著者 Hsiang-Chun Hsu; Gerard Jennhwa Chang
單位
出版者
著錄名稱、卷期、頁數 Journal of Combinatorial Optimization 28(2), p.505-510
摘要 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.
關鍵字 Balanced coloring;Balanced decomposition;Balanced decomposition number;Connectivity
語言 en_US
ISSN 1382-6905
期刊性質 國外
收錄於 SCI
產學合作
通訊作者
審稿制度
國別 USA
公開徵稿
出版型式 ,電子版
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/115405 )

SDGS 優質教育