A generalization of 0-sum flows in graphs
A generalization of 0-sum flows in graphs
复制标题
图中 0-sum 流的推广
DOI：
10.1016/j.laa.2013.01.005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Akbari,M. Kano and S. Zare
中科院分区：
文献类型：
--
作者：
M.Kano;H.Matsuda;M.Tsugaki and Guiying Yan;M. Kano and Aung Kyaw;S. Akbari,M. Kano and S. Zare
设G是一个图，H是一个交换群.对于每个子集S ∈ H，一个映射E（G）→S称为S-流。对于G的给定S-流，对任意v∈V（G），定义s（v）=∑uv∈E（G）<$（uv）.设k∈H.我们说一个图G允许一个k-和S-流，如果存在一个S-流使得对于每个顶点v，s（v）=k。本文证明了：若G是一个连通二部图，其两部分X={x1，...，xr}，Y={y1，...，ys}且c1，...，cr，d1，...，ds为真实的，则存在R-流使得s（xi）= ci且s（yj）=dj，对1 <$i <$r，1 <$j <$s当且仅当∑i= 1 rci =∑j= 1 sdj.证明了若G是连通非二部图，且c1，.，cn为任意整数，则存在Z流使得s（vi）=ci，其中i= 1，.，n当且仅当奇ci的个数为偶数.
Let G be a graph and H be an abelian group. For every subset S⊆H a map ϕ:E(G)→S is called an S-flow. For a given S-flow of G, and every v∈V(G), define s(v)=∑uv∈E(G)ϕ(uv). Let k∈H. We say that a graph G admits a k-sum S-flow if there is an S-flow such that for each vertex v,s(v)=k. We prove that if G is a connected bipartite graph with two parts X={x1,…,xr}, Y={y1,…,ys} and c1,…,cr,d1,…,dsare real numbers, then there is an R-flow such that s(xi)=ciand s(yj)=dj, for 1⩽i⩽r,1⩽j⩽s if and only if ∑i=1rci=∑j=1sdj. Also, it is shown that if G is a connected non-bipartite graph and c1,…,cnare arbitrary integers, then there is a Z-flow such that s(vi)=ci, for i=1,…,n if and only if the number of odd ciis even.