On balance in group graphs

We propose a generalization of signed graphs, called group graphs. These are graphs regarded as symmetric digraphs with a group element s ( u, v ) called the signing associated with each arc ( u, v ) such that s ( u, v ) s ( v, u ) = 1. A group graph is balanced if the product s ( v 1 , v 2 ) s ( v 2 , v 3 ) … s ( u m , v 1 ) = 1 for each cycle v 1 , v 2 ,…, v m , v 1 in the graph. Let G denote the graph, F the group (not necessarily commutative), and s the signing. Then the group graph is denoted by ( G, F, s ). Given a group graph ( G, F, s ), which need not be balanced, we define the deletion index δ( G, F, s ) as the minimum cardinality of a deletion set , which is a subset of lines whose deletion results in a balanced group graph. Similarly we define the alteration index γ( G, F, s ) as the minimum cardinality of a alteration set , which is a set of lines { u, v } in the graph the values s ( u, v ) and s ( v, u ) of which can be changed so that the new group graph is balanced. When F is the group of order 2, we obtain a signed graph. Generalizing results known for signed graphs, we prove that minimal deletion sets are minimal change sets, which implies the equality δ( G, F, s ) = γ( G, F, s ) for all G, F , and s. We also prove the in‐equality δ ( G, F, s ) ≤ ( n ‐ 1) q/n , where q is the number of lines in the graph G and n is the order of the group F. We conclude by studying δ for signed complete bigraphs K n,n when the signing is determined from a Hadamard matrix.