Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331910 | Information Processing Letters | 2015 | 5 Pages |
Abstract
A zero-sum k-flow for a graph G is a vector in the null-space of the 0,1-incidence matrix of G such that its entries belong to {±1,â¯,±(kâ1)}. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G admits a zero-sum 6-flow. (2,3)-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)-graph G has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)-graph G with n vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(logâ¡n). Furthermore, we show that it is NP-complete to determine whether a given (3,4)-semiregular graph has a zero-sum 3-flow.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ali Dehghan, Mohammad-Reza Sadeghi,