On balance in group graphs
✍ Scribed by Frank Harary; Bernt Lindström; Hans-olov Zetterström
- Publisher
- John Wiley and Sons
- Year
- 1982
- Tongue
- English
- Weight
- 300 KB
- Volume
- 12
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
We propose a generalization of signed graphs, called group graphs. These are graphs regarded as symmetric digraphs with a group element s(u, u ) called the signing associated with each arc (u, u ) such that s(u, u)s(u, u) = 1. A group graph is ba2anced if the product s(ul, u2)s(u2, ug) -.s(u,, ul) = 1 for each cycle u1, u 2 , . . . , u,, u1 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 6(G, F, s ) as the minimum cardinality of a de2etion set, which is a subset of lines whose deletion results in a balanced group graph. Similarly we define the alteration index 7(G, F, 9 ) as the minimum cardinality of a alteration set, which is a set of lines {u, u} in the graph the values s(u, u) and s(u, 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 6(G, F, s) = y(G, F, s) for all G, F, and s. We also prove the inequality 6(G, F, s) Q (nl ) 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 6 for signed complete bigraphs K,,, , , when the signing is determined from a Hadamard matrix.
📜 SIMILAR VOLUMES