ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 307-315
Balanced Abelian group-valued functions on directed graphs
Yonah Cherniavsky *
Department of Mathematics, Ariel University, Ariel, Israel
Avraham Goldstein
Borough of Manhattan Community College, CUNY, New York, USA
Vadim E. Levit
Department of Computer Science, Ariel University, Ariel, Israel
Received 5 August 2015, accepted 29 September 2016, published online 9 March 2017
We discuss functions from the edges and vertices of a directed graph to an Abelian group. A function is called balanced if the sum of its values along any cycle is zero. The set of all balanced functions forms an Abelian group under addition. We study this group in two cases: when we are allowed to walk against the direction of an edge taking the opposite value of the function and when we are not allowed to walk against the direction.
Keywords: Consistent graphs, balanced signed graphs, balanced labelings of graphs, gain graphs, weighted graphs.
Math. Subj. Class.: 05C22
1 Introduction
Let A be an Abelian group with the group operation denoted by + and the identity element denoted by 0. Let G be a graph. Roughly speaking, an A-valued function f on vertices and/or edges of G is called balanced if the sum of its values along any cycle of G is 0. Our cycles are not permitted to have repeating edges.
The study of balanced functions can be conducted in three cases:
* Corresponding author
E-mail addresses: yonahch@ariel.ac.il (Yonah Cherniavsky), avraham.goldstein.nyc@gmail.com (Avraham Goldstein), levitv@ariel.ac.il (Vadim E. Levit)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
315
Ars Math. Contemp. 13 (2017) 275-291
1.	The graph G is directed with the set of vertices V and the set of directed edges E. When traveling between the vertices, we are allowed to travel with or against the direction of the edges. The value of a function f on e, which represents traveling the edge e against its direction, is equal to -f (e). In this context, when the function is defined on edges only, the pair (G, f) is called a network or a directed network. In this paper we shall call this the flexible case, meaning that the direction of an edge does not forbid us to walk against it. The notion of balanced functions on edges for the flexible case, for functions taking values only on the edges, is introduced in the literature under different names. Thus, for example, in [1] the set of such functions is exactly Im(d), where d is the "exterior differential", which maps a function f defined on vertices to the function df on edges defined by the equality (df )(e) = f (e+) -f (e_), where e_ and e+ are the origin and the end of a directed edge e. In [11], in somewhat different language, that set is referred to as the set of consistent graphs. In [13] such functions have been introduced under the name "color-coboundaries". They also appear in literature under the name "tensions". They have been extensively studied, recent examples include [3,4, 6, 10, 14]. In [5] balanced functions on edges appear in a certain connection with geometric representations of the Coxeter group associated to a graph. In a rather common terminology introduced by Zaslavsky, [15], a pair of a graph and such a function on the edges of a graph is called a "gain graph".
2.	The graph G is directed with the set of vertices V and the set of directed edges E, but we are only allowed to travel with the direction of the edges. In this paper we shall call this the rigid case. When f takes values only on the edges then in some literature, following Serre, [12], the flexible case is described as a particular instance of the rigid case by introducing the set E as the new set of directed edges of G (the cardinality of E is twice that of E), denoting by e G E the inverse of the directed edge e G E and requiring f (e) = -f (e), [1, 12].
3.	The graph G is undirected. The value of a function f on an edge e does not depend on the direction of the travel on e. The case of balanced functions f : E ^ R is studied in [2], where these functions are called "cycle-vanishing edge valuations". The case of balanced functions f : E ^ A is studied in [7]. The case of balanced functions f : VUE ^ A is first introduced and studied in [9]. The group structure of the groups of balanced functions on the edges, balanceable functions on the vertices and balanced functions on the vertices and edges of an undirected graph with values in an Abelian group is studied in [7].
The subject of this paper is the group structure and the relations between groups of functions associated with the notion of balance on a directed graph. Namely, we study the group structures of the groups of balanced functions for the flexible and the rigid cases and the relations between these two cases.
In this article we calculate the groups of balanced functions on the edges, balanceable functions on the vertices and balanced functions on the vertices and edges of a directed graph with values in an Abelian group for both flexible and rigid cases.
In what follows, we say that a directed graph is connected if its underlying undirected graph is connected, and strongly connected whenever there exists a directed path between any ordered pair of vertices.
For the basics of Graph Theory we refer to [8].
Y. Cherniavsky, A. Goldstein and V. E. Levit: Balanced functions on directed graphs 313
2 The flexible case
Let G = (V, E) be a connected directed graph, possibly with loops and multiple edges. Let v and w be two vertices connected by an edge e; v is the origin of e and w is the endpoint of e. For e G E denote by e the same edge as e but taken in the opposite direction. Thus e goes from w to v. Let E = {e, e | e G E}.
Definition 2.1. A path from a vertex x to a vertex y is an alternating sequence vi, ei, v2, e2,...,vn, en of vertices from V and different edges from E such that v1 = x and each ej, for j = 1,..., n - 1, goes from Vj to vj+1 and en goes from vn to y. We permit the same edge e to appear in a path twice - one time along and one time against its direction, since this is regarded as using two different edges from E.
We require our graphs to be connected. Namely, any two different vertices of the graph G can be connected by a path.
Definition 2.2. A cycle is a path from a vertex to itself.
We permit the trivial cycle, which is the empty sequence containing no vertices and no edges.
Definition 2.3. The length of a cycle is the number of its edges.
Definition 2.4. A function f : E ^ A such that f (e) = —f (e) is balanced if the sum f (e1) + ... + f (en) of the values of f over all the edges of any cycle of G is equal to 0.
Definition 2.5. The set of all the balanced functions f : E ^ A is denoted by HF(E, A). HF(E, A) is a subgroup of the Abelian group AE of all the functions from E to A.
Definition 2.6. A function g : V ^ A is balanceable if there exists some f : E ^ A such that f (e) = —f (e) and the sum of all the values g(v1) + f (e1) + g(v2) + f (e2) + ... + g(vn) + f (en) along any cycle of G is zero. We say that this function f : E ^ A balances the function g : V ^ A.
Definition 2.7. The set of all the balanceable functions g : V ^ A is denoted by BF(V, A). The group BF(V, A) is a subgroup of the free Abelian group AV of all the functions from V to A.
Definition 2.8. A function h : V U E ^ A, which takes both vertices and edges of G to some elements of A, is balanced if h(e) = —h(e) and the sum of its values h(v1) + h(e1) + h(v2) + h(e2) + ... + h(vn) + h(en) along any cycle of G is zero.
Definition 2.9. The set of all the balanced functions h : V U E ^ A is denoted by WF(G, A). The group WF(G, A) is a subgroup of the Abelian group AV U E of all the functions from V E to A.
Clearly, any balanced function f g HF(E, A) can be viewed as a balanced function from V U E to A, which takes zero value on every vertex of G. Thus, we will regard HF(E, A) as a subgroup of WF(V U E, A).
Proposition 2.10. The quotient WF(VU E, A)/HF(E, A) is naturally isomorphic to BF (V, A).
74
Ars Math. Contemp. 13 (2017) 275-291
Proof. The natural isomorphism is defined by "forgetting" the values of h e WF(V |J E, A) on the edges of G and regarding it just as a balanceable function from V to A. □
We review some basic definitions and facts regarding Abelian groups.
Definition 2.11. A natural number k is the order of an element a e A if it is the minimal positive integer such that k • a = 0.
Definition 2.12. The set of all elements of A of order 2 is denoted by A2. The set A2 is a subgroup of A.
We provide a proof of a folklore result which describes the structure of the group
HF (E, A).
Proposition 2.13. The group HF(E, A) is isomorphic to A|VI-1.
Proof. Select a vertex v and consider the following bijection between the group of all A-valued functions g on V with g(v) = 0 and the group HF(E, A). For any such g, since each edge e e E goes from some vertex x to some vertex y, we define f (e) = g(y) - g(x). A straightforward calculation shows that f e HF(E, A). In the other direction of the bijection, for f e HF(E, A) we inductively construct the function g as follows: we set g(v) = 0; if g(u) has been defined for a vertex u then for every vertex w, for which there exists some edge e from u to w, we define g(w) = g(u) + f (e). Since f e HF(E, A), any two calculations of the value of g on any vertex u will produce the same result. The connectivity implies that every vertex indeed receives a value. Thus, our g is well-defined. Obviously, the bijection, constructed above, is a group isomorphism.	□
Now we can state and prove one of our main results.
Theorem 2.14. Let G = (V, E) be a connected directed graph and G' be its underlying undirected graph. Then:
1.	If G' is bipartite, then the group WF(V |J E, A) is isomorphic to A|V|.
2.	If G' is not bipartite, then WF(V |J E, A) is isomorphic to A2 x A|V|-1.
Proof. If G consists only of one vertex then part (1) of our theorem is trivial. Otherwise, let us look at any one non-loop edge of G as it is depicted in Fig. 1:
p i a-b
Figure 1: An edge with values on it and on its origin and end.
The letters on the edge and the vertices denote the values of a function h : V |J E ^ A. Assume that h is balanced, that is, h e WF(V |J E, A). Then for the cycle obtained by walking along this edge and returning back along it we have the following equation:
a +p + b —p = 0 ,
which immediately implies that
b = — a .
Y. Cherniavsky, A. Goldstein and V. E. Levit: Balanced functions on directed graphs 313
Thus h must have opposite values on any two vertices of G connected by an edge. Assume that G' is bipartite, which implies that G has no cycles of odd length. Then h, restricted to the edges, must be equal to some balanced function f e HF(E, A) on the edges, since values a and —a on the vertices of an even-length cycle appear equally often. Now select any vertex v e V. We can construct a balanced function h on vertices and edges by: for any element a e A define h(v) = a and then define h for all the neighbors of v to be —a and then for all the neighbors of the neighbors of v define h to be a and so on. Continuing this way we will assign values a or —a to all the vertices of G. Since all the cycles are of even length, we will not get a contradiction in that process. Next we choose any function f e HF(E, A) and we set h on the edges to be equal to f. Hence, we have constructed a bijection between WF(V|J E, A) and the group of pairs {(a,f) | a e A, f e HF(E, A)}. This bijection is obviously also a group isomorphism. In addition, {(a, f) | a e A, f e HF(E, A)} is isomorphic to A|V|, since the group HF(E, A) is isomorphic to A|V|-1 by Proposition 2.13.
Now assume that G' is not bipartite, that is, G has a cycle of odd length. As we have already seen above, the values of a balanced function h e WF(V U E, A) on the vertices must be a and —a for some a e A. But walking along a cycle of odd length with vertices vi, v2,...,vn, we get h(vi) = a, h(v2) = —a,..., h(vn) = a, h(vi) = —a, so a = —a, that is, 2a = 0, which exactly means that a e A2. Thus we construct a bijection between WF(V dlE, A) and the group of pairs {(a, f) | a e A2, f e HF(E, A)} mapping h e WF(V U E, A) to the pair (a, f), where a e A2 is the value of h on any vertex, and f is a balanced function on edges defined as f (e) = h(e) + a for every edge e; conversely, from a given a e A2 and a balanced function f e HF(E, A), we can construct a balanced function h e WF(V |J E, A) assuming h(v) = a for any vertex v and h(e) = f (e) + a for any edge e. This bijection is a group isomorphism. In addition, {(a, f) | a e A2, f e HF(E, A)} is isomorphic to A2 x A|V|-1, since the group HF(E, A) is isomorphic to A|V|-1 by Proposition 2.13.	□
Remark 2.15. Let G = (V, E) be a connected directed graph and G' be its underlying undirected graph. Notice that if the graph G' is bipartite, then the group of balanceable functions BF(V, A) is isomorphic to A and if G' is not bipartite, then the group of bal-anceable functions BF(V, A) is isomorphic to A2 - the group of involutions of A.
3 The rigid case
Let G = (V, E) be a connected directed graph. Recall that in the rigid case we are allowed to walk only in the direction of an edge but not against it. It naturally changes the notion of a path and of a cycle in comparison with the flexible case.
Definition 3.1. A path from a vertex x to a vertex y is an alternating sequence v1, e1, v2, e2,...,vn, en of vertices from V and different edges from E (and not E) such that v1 = x and each ej, for j = 1,..., n — 1, goes from vj to vj+1 and en goes from vn to y.
For example, the triangle depicted in Fig. 2 is a cycle in the flexible case but is not a cycle in the rigid case.	d
Similarly to the flexible case denote by BR(V, A), HR(E, A) and WR(V || E, A) the groups of balanceable functions on vertices, balanced functions on edges and balanced functions of the entire graph G (vertices and edges), respectively.
76
Ars Math. Contemp. 13 (2017) 275-291
Figure 2: A flexible cycle, which is not a rigid cycle.
Proposition 3.2. Every function on the set of vertices is balanceable. That is,
BR(V,A) = AV.
Proof. Let us take a function g : V ^ A. Define the function h : V |J E ^ A in the following way: h(v) = g(v) for each vertex v G V, h(e) = —g(v) for all the edges e G E which start at v. Obviously h is a balanced function.	□
Definition 3.3. Two vertices x and y of G are strongly connected if there exists a path P1 from x to y and a path P2 from y to x. We also say that every vertex is strongly connected to itself.
Notice that we allow Pi and P2 to have common edges.
Definition 3.4. A cycle is a path P from a vertex x to itself.
Notice that, since the paths Pi and P2 mentioned above might have common edges, Pi followed by P2 may not be a cycle. It can even happen, that there exists no cycle, which contains both x and y. To illustrate it, consider the following.
Example 3.5. Consider the graph G depicted in Fig. 3 with V(G) = {x, v, w, y} and
E(G) = {e1, e2, e3, e4, e5}. The path P1 = x, e1, v, e5, w, e4 is the only path which goes from x to y and the path P2 = y, e2, v, e5, w, e3 is the only path which goes from y to x. They have a common edge e5. Thus, according to Definitions 3.1 and 3.4, there exists no cycle containing both x and y.
Figure 3: The vertices x, y are strongly connected but no cycle contains both of them.
Strong connectivity defines an equivalence relation on the vertices of G. The equivalence classes of strongly connected vertices, together with all the edges between the vertices of each class, are called the strongly connected components of G. We denote the number
Y. Cherniavsky, A. Goldstein and V. E. Levit: Balanced functions on directed graphs 313
of strongly connected components of G by k(G). Obviously, G is strongly connected if and only if k(G) = 1.
Lemma 3.6. If G is strongly connected, thenthe group HR(E, A) is isomorphic to A|V I-1, just like in the flexible case.
Proof. Let E = {e1,...,en}. The edge e1 goes from some x to some y. There is a path P which goes from y to x and does not contain e1, since if P contains e1 we can just delete this e1 and all the vertices and edges that come after it from P. Thus, the sum of values of any f e HR(E, A) along P must be equal to —f (e1). Hence, we can add a new edge k1 to G which goes from y to x and we can extend the function f to a balanced function on the edges of the new G if and only if we set f (k1) = —f (e1). So the group of the balanced functions on the edges of G after the addition of ek1 is naturally isomorphic to the original group of the balanced functions on the edges of G before the addition. Repeating this process for all the edges of E we reduce G to the flexible case, while not changing the group of the balanced functions on the edges of G.	□
Theorem 3.7. The group HR(E, A) is isomorphic to A|V|-fc(G)+r(G), where k(G) is the number of strongly connected components of G, and r(G) is the number of all the edges in G which go from a vertex in one strongly connected component of G to a vertex in a different strongly connected component of G.
Proof. Let V1,..., Vt be the equivalence classes of vertices of G with respect to strong connectivity. Denote the set of edges between the vertices of Vj by Ej. Obviously, f e
HR(E, A) if and only if f |e, e HR(Ej, A) for each j, 1 < j < t. Thus, HR(E, A) = HR(E1, A) x • • • x HR(Et, A) x AU, where U is the set of all the edges between the vertices in different strongly connected components of G. By Lemma 3.6 we conclude that
HR(E, A) is isomorphic to A|Vi|-1+|V2|-1+-+|V'|-1+r(G) = A|VM(G)+r(G). □
Theorem 3.8. The group WR(V U E, A) is isomorphic to A2|VM(G)+r(G), where k(G) is the number of strongly connected components of G, and r(G) is the number of all the edges in G which go from a vertex in one strongly connected component of G to a vertex in a different strongly connected component of G.
Proof. To each h e WR(V |J E, A) there corresponds the pair (g, f), where g e BR(V, A) is just the restriction of h on the vertex set, and the value of f e HR(E, A) on every edge e is equal to h(e) + h(v), where the vertex v is the origin of the edge e. Such a function f is obviously a balanced function on the edge set since its value along any path is equal to the value of h along that path. This correspondence between the elements of WR( V |J E, A) and the pairs from BR(V, A) x HR(E, A) is a bijection. Indeed, for a given pair (g, f), where g is any function on the vertex set and f is a balanced function on the edge set, we can construct h : VUE ^ A as follows: h(v) = g(v) for all v e V and h(e) = f (e) — g(v) for all e e E, where the vertex v is the origin of the edge e. The constructed bijection is obviously a group isomorphism between the group WR(V |J E, A) and the group BR(V, A) x HR(E, A), which is isomorphic to A|V 1 x
A|V |-fc(G)+r(G).	□
Thus, the flexible problem for a graph G = (V, E) can be regarded as the rigid problem for the graph G' = (V, E), where E = {e, k | e e E}. Vice versa, the rigid problem for a graph G can be regarded as a free product of the rigid problems for the strongly connected
78
Ars Math. Contemp. 13 (2017) 275-291
components of G also multiplied by Ar(G) where r(G) is the number of edges between different strongly connected components of G.
The following simple claim connects this work to [7].
Proposition 3.9. Let G be an undirected connected graph and let Gdir be a directed graph obtained from G by any assignment of directions to the edges of G. Denote by H(E,A) the group of A-valued balanced functions on edges of G. Choose any order on edges of G and embed H(E, A) and HR(E(Gdir),A) into AIEI. For an undirected graph G the group of balanced functions on edges of G is equal to the intersection of all the groups HR(E(Gdir),A), where Gdir runs over all directed graphs for all 2IEI possible direction assignments to the edges of G. The same is true for the groups of balanced functions on the entire graph (both vertices and edges). Namely, W(V[JE,A) = D WR(V{jE(Gdir), A).
Proof. Let Cyc = v1,e1,..., vk, ek be a cycle in the undirected graph G. There exists a directed graph Gdir for which c is also a cycle. So any f G p| HR(E(Gdir),A) must satisfy the equation J2i=1 f (ei) = 0. Therefore f G H(E, A), since Cyc is an arbitrary cycle of G. Hence,
H(E, A) D p| HR(E(Gdir),A).
The opposite inclusion is obvious, since any cycle of any Gdir is a cycle of G. The proof of the second statement of the proposition is similar.	□
Acknowledgment
The authors are grateful to the anonymous referee for helpful comments that improve the presentation.
References
[1]	R. Bacher, P. de la Harpe and T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France 125 (1997), 167-198, http://www. numdam.org/item?id=BSMF_1997_125_2_16 7_0.
[2]	R. Balakrishnan and N. Sudharsanam, Cycle-vanishing edge valuations of a graph, Indian J. PureAppl. Math. 13 (1982), 313-316.
[3]	M. Beck, F. Breuer, L. Godkin and J. L. Martin, Enumerating colorings, tensions and flows in cell complexes, J. Combin. Theory Ser. A 122 (2014), 82-106, doi:10.1016/j.jcta.2013.10.002, http://dx.doi.Org/10.1016/j.jcta.2013.10.002.
[4]	F. Breuer and A. Dall, Bounds on the coefficients of tension and flow polynomials, J. Algebraic Combin. 33 (2011), 465-482, doi:10.1007/s10801-010-0254-4, http://dx.doi. org/10.1007/s10801-010-0254-4.
[5]	V. Bugaenko, Y. Cherniavsky, T. Nagnibeda and R. Shwartz, Weighted Coxeter graphs and generalized geometric representations of Coxeter groups, Discrete Appl. Math. 192 (2015), 1727, doi:10.1016/j.dam.2014.05.012, http://dx.doi.org/10.1016/j.dam.2014. 05.012.
[6]	B. Chen, Orientations, lattice polytopes, and group arrangements. I. Chromatic and tension polynomials of graphs, Ann. Comb. 13 (2010), 425-452, doi:10.1007/s00026-009-0037-6, http://dx.doi.org/10.1007/s0002 6-00 9-0037-6.
Y. Cherniavsky, A. Goldstein and V. E. Levit: Balanced functions on directed graphs 313
[7]	Y. Cherniavsky, A. Goldstein and V. E. Levit, Groups of balanced labelings on graphs, Discrete Math. 320 (2014), 15-25, doi:10.1016/j.disc.2013.12.003, http://dx.doi.org/ 10.1016/j.disc.2013.12.003.
[8]	R. Diestel, Graph theory, volume 173 of Graduate Texts in Mathematics, Springer, Heidelberg, 5th edition, 2016.
[9]	M. Joglekar, N. Shah and A. A. Diwan, Balanced group-labeled graphs, Discrete Math. 312 (2012), 1542-1549, doi:10.1016/j.disc.2011.09.021, http://dx.doi.org/10.1016/ j.disc.2011.09.021.
[10]	M. Kochol, Tension polynomials of graphs, J. GraphTheory 40 (2002), 137-146, doi:10.1002/ jgt.10038, http://dx.doi.org/10.1002/jgt.10038.
[11]	M. Kreissig and B. Yang, Efficient synthesis of consistent graphs, in: Proceedings of the 18th European Signal Processing Conference EUSIPCO - 2010, Aalborg, Denmark, pp. 1364-1368, 2010, http://www.iss.uni-stuttgart.de/forschung/ veroeffentlichungenZkreissig_eusipco10.pdf.
[12]	J.-P. Serre, Arbres, amalgames, SL2, Societe Mathematique de France, Paris, 1977.
[13]	W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math. 6 (1954), 80-91.
[14]	D. R. Woodall, Tutte polynomial expansions for 2-separable graphs, Discrete Math. 247 (2002), 201-213, doi:10.1016/S0012-365X(01)00177-7, http://dx.doi.org/10. 1016/S0 012-3 65X(01)00177-7.
[15]	T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin. (2012), Dynamic Surveys 8, http://www.combinatorics.org/issue/ view/Surveys.