𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


On Balanced Graphs
✍ Flavia Bonomo; Guillermo Durán; Min Chih Lin; Jayme L Szwarcfiter 📂 Article 📅 2005 🏛 Springer-Verlag 🌐 English ⚖ 242 KB
On Group Connectivity of Graphs
✍ Hong-Jian Lai; Rui Xu; Ju Zhou 📂 Article 📅 2008 🏛 Springer Japan 🌐 English ⚖ 133 KB
Group testing in graphs
✍ Justie Su-tzu Juan; Gerard J. Chang 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 259 KB