| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 426995 | Information Processing Letters | 2016 | 8 Pages |
•A zero-sum vertex k-flow is a vector in the null space of the 0,1-adjacency matrix of G such that its entries belong to {±1,⋯,±(k−1)}{±1,⋯,±(k−1)}.•We show that there is a polynomial time algorithm to determine whether a given graph G has a zero-sum edge-coloring.•We show that for a given bipartite (2,3)(2,3)-graph G, it is NP-complete to determine whether G has a zero-sum vertex 3-flow.
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)}{±1,⋯,±(k−1)}. Also, a zero-sum vertex k-flow is a vector in the null space of the 0,1-adjacency matrix of G such that its entries belong to {±1,⋯,±(k−1)}{±1,⋯,±(k−1)}. Furthermore, a zero-sum k-edge-coloring of a simple 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)}{±1,⋯,±(k−1)} and this vector is a proper edge coloring (adjacent edges receive distinct colors) for G. In this work, we show that there is a polynomial time algorithm to determine whether a given graph G has a zero-sum edge-coloring. Also, we prove that there is no constant bound k, such that for a given bipartite graph G, if G has a zero-sum vertex flow, then G has a zero-sum vertex k -flow. Furthermore, we show that for a given bipartite (2,3)(2,3)-graph G, it is NP-complete to determine whether G has a zero-sum vertex 3-flow.
