Balanced decomposition of a vertex-colored graph
Balanced decomposition of a vertex-colored graph
复制标题
DOI：
10.1016/j.dam.2008.01.006
复制
发表时间：
2008-11
期刊：
影响因子：
--
通讯作者：
S. Fujita;Tomoki Nakamigawa
中科院分区：
文献类型：
--
作者：
S. Fujita;Tomoki Nakamigawa
图G的平衡点染色是从V（G）到{− 1，0，1}的函数c使得∑{c（v）：v∈V（G）}=0。称V（G）的一个子集U为平衡集，如果U诱导一个连通子图且∑{c（v）：v∈U}=0.一个分解V（G）=V1 <$Vis称为平衡分解，如果Vi是1≤i≤r的平衡集.本文引入了图G的平衡分解数f（G），f（G）是使对G的任一平衡点染色c，存在平衡分解V（G）=V1 Vr的最小整数s，|Vi|对于1≤i≤r，≤s。研究了完全图、树、完全二部图、圈、2-连通图等基本图族的平衡分解数。
A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V1∪⋯∪Vris called a balanced decomposition if Viis a balanced set for 1≤i≤r. In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V1∪⋯∪Vrwith |Vi|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.