Constant Sum Group Flows of Graphs

As an analogous concept of a nowhere-zero flow for directed graphs, zero-sum flows and constant-sum flows are defined and studied in the literature. For an undirected graph, a zero-sum flow (constant-sum flow resp.) is an assignment of nonzero integers to the edges such that the sum of the values of all edges incident with each vertex is zero (constant h resp.), and we call it a zero-sum k -flow ( h -sum k -flow resp.) if the values of the edges are less than k . We extend these concepts to general constant-sum A -flow, where A is an Abelian group, and consider the case A = Z k the additive Abelian cyclic group of integer congruences modulo k with identity 0. In the literature, a graph is alternatively called Z k -magic if it admits a constant-sum Z k -flow, where the constant sum is called a magic sum or an index for short. We define the set of all possible magic sums such that G admits a constant-sum Z k -flow to be I k ( G ) and call it the magic sum spectrum, or for short, the index set of G with respect to Z k . In this article, we study the general properties of the magic sum spectrum of graphs. We determine the magic sum spectrum of complete bipartite graphs K m , n for m ≥ n ≥ 2 as the additive cyclic subgroups of Z k generated by k d , where d = g c d ( m − n , k ) . Also, we show that every regular graph G with a perfect matching has a full magic sum spectrum, namely, I k ( G ) = Z k for all k ≥ 3 . We characterize a 3-regular graph so that it admits a perfect matching if and only if it has a full magic sum spectrum, while an example is given for a 3-regular graph without a perfect matching which has no full magic sum spectrum. Another example is given for a 5-regular graph without a perfect matching, which, however, has a full magic sum spectrum. In particular, we completely determine the magic sum spectra for all regular graphs of even degree. As a byproduct, we verify a conjecture raised by Akbari et al., which claims that every connected 4 k -regular graph of even order admits a 1-sum 4-flow. More open problems are included.