A group representation approach to balance of gain graphs
- PDF / 646,951 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 181 Views
A group representation approach to balance of gain graphs Matteo Cavaleri1 · Daniele D’Angeli1 · Alfredo Donno1 Received: 4 February 2020 / Accepted: 28 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study the balance of G-gain graphs, where G is an arbitrary group, by investigating their adjacency matrices and their spectra. As a first step, we characterize switching equivalence and balance of gain graphs in terms of their adjacency matrices in Mn (CG). Then we introduce a represented adjacency matrix, associated with a gain graph and a group representation, by extending the theory of Fourier transforms from the group algebra CG to the algebra Mn (CG). We prove that, anytime G admits a finite-dimensional faithful unitary representation π , a G-gain graph is balanced if and only if the spectrum of the represented adjacency matrix associated with π coincides with the spectrum of the underlying graph, with multiplicity given by the degree of the representation. We show that the complex adjacency matrix of complex unit gain graphs and the adjacency matrix of a cover graph are indeed particular cases of our construction. This enables us to recover some classical results and prove some new characterizations of balance in terms of spectrum, index or structure of these graphs. Keywords Gain graph · Balance · Adjacency matrix · Spectrum · Cover graph · Group representation · Fourier transform Mathematics Subject Classification 05C22 · 05C25 · 05C50 · 20C15 · 43A32
The second author thanks the Austrian Science Fund project FWF P29355-N35.
B
Alfredo Donno [email protected] Matteo Cavaleri [email protected] Daniele D’Angeli [email protected]
1
Università degli Studi Niccolò Cusano, Via Don Carlo Gnocchi, 3, 00166 Rome, Italy
123
Journal of Algebraic Combinatorics
1 Introduction A G-gain graph is a graph where an element (a gain) of a group G is assigned to each oriented edge, in such a way that the inverse element is associated with the opposite orientation. Gain graphs can be regarded as a generalization of signed graphs, where the group is {−1, 1}, extensively studied even beyond the graph theory (see [33] for an extended and periodically updated bibliography). Gain graphs can be also considered as particular cases of biased graphs [29], which are graphs where a special subset of circles is selected. The notion of gain graph is also strictly related to that of voltage graph: however, the theory of voltage graphs especially moves toward graph-coverings (see [11]) whereas among the key notions concerning signed and gain graphs there are switching equivalence and balance (see, for instance, [12,29]). In this paper, we are interested in studying the balance property for gain graphs on an arbitrary group, via a spectral investigation which is realized by using group representation theory and a Fourier transform approach. The balance of signed graphs can be characterized in several equivalent ways: the positiveness of circles, the switching equ
Data Loading...
