Signed Graphs: From Modulo Flows to Integer-Valued Flows
Signed Graphs: From Modulo Flows to Integer-Valued Flows
复制标题
DOI：
10.1137/17m1126072
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Jian Cheng;You Lu;Rong Luo;Cun-Quan Zhang
中科院分区：
文献类型：
--
作者：
Jian Cheng;You Lu;Rong Luo;Cun-Quan Zhang
模流到整值流的转换是整数流研究中最关键的步骤之一。Tutte和Jaeger的开创性工作证明了普通图的模流和整值流的等价性。然而，这种等价性对于带符号的图不再成立。这促使我们研究如何将带符号图的模流转换为整值流。在本文中，我们推广了Xu和Zhang(离散数学，~299,2005)，Schubert和Steffen(European J.Combin，~48,2015)和朱(J.Combin，2015)的一些早期结果。理论系列。B~112,2015)，并证明了对于有符号图，每个模$(2+\FRAC{1}{p})$-流都可以转换/扩展为整数值流。
Converting modulo flows into integer-valued flows is one of the most critical steps in the study of integer flows. Tutte and Jaeger's pioneering work shows the equivalence of modulo flows and integer-valued flows for ordinary graphs. However, such equivalence does not hold any more for signed graphs. This motivates us to study how to convert modulo flows into integer-valued flows for signed graphs. In this paper, we generalize some early results by Xu and Zhang (Discrete Math.~299, 2005), Schubert and Steffen (European J. Combin.~48, 2015), and Zhu (J. Combin. Theory Ser. B~112, 2015), and show that, for signed graphs, every modulo $(2+\frac{1}{p})$-flow with $p \in {\mathbb Z}^+ \cup \{\infty\}$ can be converted/extended into an integer-valued flow.