Search

We reinterpret the Rhodes semilattices R n (G) of a group G in terms of gain graphs and generalize them to all gain graphs, both as sets of partition-potential pairs and as sets of subgraphs, and for the latter, further to biased graphs. Based on this we propose four different natural lattices in which the Rhodes semilattices and its generalizations are order ideals. [ABSTRACT FROM AUTHOR]

Let Φ = (G, ϕ) be a -gain graph. In this paper, we will prove that there are no -gain graphs with the rank 2m(G) - 2c(G) + 1, where c(G) is the dimension of cycle space of G, m(G) is the matching number of G. For a given c(G), we also prove that there are innitely many connected -gain graphs with the rank 2m(G)-2c(G)+s, (0 ⩽ s ⩽ 3c(G), s ̸= 1). These results can also apply to undirected graphs, signed graphs and mixed graphs. [ABSTRACT FROM AUTHOR]

A complex unit gain graph (or T{\mathbb{T}}-gain graph) Γ=(G,γ)\Gamma =\left(G,\gamma ) is a gain graph with gains in T{\mathbb{T}}, the multiplicative group of complex units. The T{\mathbb{T}}-outgain in Γ\Gamma of a vertex v∈Gv\in G is the sum of the gains of all the arcs originating in vv. A T{\mathbb{T}}-gain graph is said to be an aa-T{\mathbb{T}}-regular graph if the T{\mathbb{T}}-outgain of each of its vertices is equal to aa. In this article, it is proved that aa-T{\mathbb{T}}-regular graphs exist for every a∈Ra\in {\mathbb{R}}. This, in particular, means that every real number can be a T{\mathbb{T}}-gain graph eigenvalue. Moreover, denoted by Ω(a)\Omega \left(a) the class of connected T{\mathbb{T}}-gain graphs whose largest eigenvalue is the real number aa, it is shown that Ω(a)\Omega \left(a) is nonempty if and only if aa belongs to {0}∪[1,+∞)\left\{0\right\}\cup \left[1,+\infty ). In order to achieve these results, non-complete extended pp-sums and suitably defined joins of T{\mathbb{T}}-gain graphs are considered.

We introduce the Burnside chromatic polynomial of a graph that is invariant under a group action. This is a generalization of the Q-chromatic function Zaslavsky introduced for gain graphs. Given a group 𝕲 acting on a graph G and a 𝕲-set X, a proper X-coloring is a function with no monochromatic edge orbit. The set of proper colorings is a 𝕲-set which induces a polynomial function from the Burnside ring of 𝕲 to itself. In this paper, we study many properties of the Burnside chromatic polynomial, answering some questions of Zaslavsky.

We define GG-cospectrality of two GG-gain graphs (Γ,ψ)\left(\Gamma ,\psi ) and (Γ′,ψ′)\left(\Gamma ^{\prime} ,\psi ^{\prime} ), proving that it is a switching isomorphism invariant. When GG is a finite group, we prove that GG-cospectrality is equivalent to cospectrality with respect to all unitary representations of GG. Moreover, we show that two connected gain graphs are switching equivalent if and only if the gains of their closed walks centered at an arbitrary vertex vv can be simultaneously conjugated. In particular, the number of switching equivalence classes on an underlying graph Γ\Gamma with nn vertices and mm edges, is equal to the number of simultaneous conjugacy classes of the group Gm−n+1{G}^{m-n+1}. We provide examples of GG-cospectral switching nonisomorphic graphs and we prove that any gain graph on a cycle is determined by its GG-spectrum. Moreover, we show that when GG is a finite cyclic group, the cospectrality with respect to a faithful irreducible representation implies the cospectrality with respect to any other faithful irreducible representation, and that the same assertion is false in general.

A complex unit gain graph is a simple graph in which each orientation of an edge is given a complex number with modulus 1 and its inverse is assigned to the opposite orientation of the edge. In this article, first we establish bounds for the eigenvalues of the complex unit gain graphs. Then we study some of the properties of the adjacency matrix of a complex unit gain graph in connection with the characteristic and the permanental polynomials. Then we establish spectral properties of the adjacency matrices of complex unit gain graphs. In particular, using Perron–Frobenius theory, we establish a characterization for bipartite graphs in terms of the set of eigenvalues of a gain graph and the set of eigenvalues of the underlying graph. Also, we derive an equivalent condition on the gain so that the eigenvalues of the gain graph and the eigenvalues of the underlying graph are the same. [ABSTRACT FROM AUTHOR]

Let 𝕋4 = {±1, ±i} be the subgroup of 4-th roots of unity inside 𝕋, the multiplicative group of complex units. A complex unit gain graph Φ is a simple graph Γ = (V (Γ) = {v1, . . . , vn}, E(Γ)) equipped with a map ϕ:E→(Γ)→𝕋\varphi :\vec E(\Gamma ) \to \mathbb{T} defined on the set of oriented edges such that ϕ(vivj) = ϕ(vjvi)−1. The gain graph Φ is said to be balanced if for every cycle C = vi1vi2vikvi1 we have ϕ(vi1vi2)ϕ(vi2vi3) ϕ(vikvi1) = 1.

It is an open question to give a combinatorial interpretation of the Falk invariant of a hyperplane arrangement, i.e., the third rank of successive quotients in the lower central series of the fundamental group of the arrangement. In this article, we give a combinatorial formula for this invariant in the case of hyperplane arrangements that are complete lift representations of certain gain graphs. As a corollary, we compute the Falk invariant for the cone of the braid, Shi, Linial, and semiorder arrangements. [ABSTRACT FROM AUTHOR]

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 M n (C G) . 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 C G to the algebra M n (C G) . 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. [ABSTRACT FROM AUTHOR]

A quaternion unit gain graph is a graph where each orientation of an edge is given a quaternion unit, and the opposite orientation is assigned the inverse of this quaternion unit. In this paper, we provide a combinatorial description of the determinant of the Laplacian matrix of a quaternion unit gain graph by using row-column noncommutative determinants recently introduced by one of the authors. A numerical example is presented for illustrating our results. [ABSTRACT FROM AUTHOR]

A gain graph over a group G , also referred to as G -gain graph, is a graph where an element of a group G , called gain, 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, among others. In this work, we show a new switching method to construct cospectral gain graphs. Some previous methods known for graph cospectrality follow as a corollary of our results. [ABSTRACT FROM AUTHOR]

Let G be an arbitrary group. We define a gain-line graph for a gain graph (Γ , ψ) through the choice of an incidence G -phase matrix inducing ψ. We prove that the switching equivalence class of the gain function on the line graph L (Γ) does not change if one chooses a different G -phase inducing ψ or a different representative of the switching equivalence class of ψ. In this way, we generalize to any group some results proven by N. Reff in the abelian case. The investigation of the orbits of some natural actions of G on the set H Γ of G -phases of Γ allows us to characterize gain functions on Γ, gain functions on L (Γ) , their switching equivalence classes and their balance property. The use of group algebra valued matrices plays a fundamental role and, together with the matrix Fourier transform, allows us to represent a gain graph with Hermitian matrices and to perform spectral computations. Our spectral results also provide some necessary conditions for a gain graph to be a gain-line graph. [ABSTRACT FROM AUTHOR]

Given a group Γ of order at most six, we characterize the graphs that have Γ -antivoltages and also determine the list of minor-minimal graphs that have no Γ -antivoltage. Our characterizations yield polynomial-time recognition algorithms for such graphs. [ABSTRACT FROM AUTHOR]

The gain graphs are essential generalizations of the signed graphs. They are indeed directed graphs whose edges are labeled by the elements of a group rather than just ±1. In this paper, we prove the existence of matroids arising from these graphs. Further, we study the structure of the obtained matroids as well as their relation with the generalized Hamming weights, the regularity of the ideal of circuits, and the codes. [ABSTRACT FROM AUTHOR]

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]

Assur graphs are a tool originally developed by mechanical engineers to decompose mechanisms for simpler analysis and synthesis. Recent work has connected these graphs to strongly directed graphs and decompositions of the pinned rigidity matrix. Many mechanisms have initial configurations, which are symmetric, and other recent work has exploited the orbit matrix as a symmetry adapted form of the rigidity matrix. This paper explores how the decomposition and analysis of symmetric frameworks and their symmetric motions can be supported by the new symmetry adapted tools.

Given a group Γ and a biased graph ( G , B ) , we define a what is meant by a Γ-realization of ( G , B ) and a notion of equivalence of Γ-realizations. We prove that for a finite group Γ and t ≥ 3 , there are numbers n ( Γ ) and n ( Γ , t ) such that the number of Γ-realizations of a vertically 3-connected biased graph is at most n ( Γ ) and that the number of Γ-realizations of a nonseparable biased graph without a ( 2 C t , ∅ ) -minor is at most n ( Γ , t ) . Other results pertaining to contrabalanced biased graphs are presented as well as an analogue to Whittle's Stabilizer Theorem for Γ-realizations of biased graphs. [ABSTRACT FROM AUTHOR]

A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph is studied. For a particular family of gain graphs with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph. [ABSTRACT FROM AUTHOR]

Given a bicircular matroid B ( G ) and q ∈ { 4 , 5 } , we characterize when the bicircular matroid B ( G ) is G F ( q ) -representable by precisely describing the structure of G . These descriptions yield polynomial-time algorithms with input G to certify if B ( G ) is or is not G F ( q ) -representable. [ABSTRACT FROM AUTHOR]

A fundamental theorem of Laman characterises when a bar-joint framework realised generically in the Euclidean plane admits a non-trivial continuous deformation of its vertices. This has recently been extended in two ways. Firstly to frameworks that are symmetric with respect to some point group but are otherwise generic, and secondly to frameworks in Euclidean 3-space that are constrained to lie on 2-dimensional algebraic varieties. We combine these two settings and consider the rigidity of symmetric frameworks realised on such surfaces. First we establish necessary conditions for a framework to be symmetry-forced rigid for any group and any surface by setting up a symmetry-adapted rigidity matrix for such frameworks and by extending the methods in Jordán et al. (2012) to this new context. This gives rise to several new symmetry-adapted rigidity matroids on group-labelled quotient graphs. In the cases when the surface is a sphere, a cylinder or a cone we then also provide combinatorial characterisations of generic symmetry-forced rigid frameworks for a number of symmetry groups, including rotation, reflection, inversion and dihedral symmetry. The proofs of these results are based on some new Henneberg-type inductive constructions on the group-labelled quotient graphs that correspond to the bases of the matroids in question. For the remaining symmetry groups in 3-space-as well as for other types of surfaces-we provide some observations and conjectures. [ABSTRACT FROM AUTHOR]

Assur graphs are a tool originally developed by mechanical engineers to decompose mechanisms for simpler analysis and synthesis. Recent work has connected these graphs to strongly directed graphs and decompositions of the pinned rigidity matrix.Many mechanisms have initial configurations, which are symmetric, and other recent work has exploited the orbit matrix as a symmetry adapted form of the rigidity matrix. This paper explores how the decomposition and analysis of symmetric frameworks and their symmetric motions can be supported by the new symmetry adapted tools. [ABSTRACT FROM AUTHOR]

Abstract: A weighted directed graph is a directed graph G whose underlying undirected graph is simple and whose edges have nonzero (directional) complex weights, that is, the presence of an edge of weight is as good as the presence of the edge with weight , the complex conjugate of . Let G be a weighted directed graph on vertices . Denote by the weight of an edge . The adjacency matrix of G is an matrix with entries or or 0, depending on whether or or otherwise, respectively. We supply a characterization of those unicyclic weighted directed graphs G whose edges have weights from the set and whose adjacency matrix satisfies the following property: ‘λ is an eigenvalue of with multiplicity k if and only if is an eigenvalue of with the same multiplicity’. [Copyright &y& Elsevier]

Abstract: A periodic graph in dimension is a directed graph with a free action of with only finitely many orbits. It can conveniently be represented in terms of an associated finite graph with weights in , corresponding to a -bundle with connection. Here we use the weight sums along cycles in this associated graph to construct a certain polytope in , which we regard as a geometrical invariant associated to the periodic graph. It is the unit ball of a norm on describing the large-scale geometry of the graph. It has a physical interpretation as the set of attainable velocities of a particle on the graph which can hop along one edge per timestep. Since a polytope necessarily has distinguished directions, there is no periodic graph for which this velocity set is isotropic. In the context of classical physics, this can be viewed as a no-go theorem for the emergence of an isotropic space from a discrete structure. [Copyright &y& Elsevier]

Abstract: A complex unit gain graph is a graph where each orientation of an edge is given a complex unit, which is the inverse of the complex unit assigned to the opposite orientation. We extend some fundamental concepts from spectral graph theory to complex unit gain graphs. We define the adjacency, incidence and Laplacian matrices, and study each of them. The main results of the paper are eigenvalue bounds for the adjacency and Laplacian matrices. [Copyright &y& Elsevier]

A gain graph is a graph where the edges are given some orientation and labeled with the elements (called gains) from a group so that gains are inverted when we reverse the direction of the edges. A signed graph with labels from the multiplicative group {1,–1} on the edges can be taken as a particular case of a gain graph. In this article, we extend the definition of certain operations on graphs, such as NEPS and composition, to gain graphs and characterize balance in such products of gain graphs. Also we analyze the adjacency matrices and eigenvalues of these products when the underlying group for labeling the edges of the gain graphs is the multiplicative group of a field. [ABSTRACT FROM AUTHOR]

Abstract: A gain graph is a graph where the edges are given some orientation and labeled with the elements (called gains) from a group so that gains are inverted when we reverse the direction of the edges. A signed graph with labels from the multiplicative group on the edges can be taken as a particular case of a gain graph. In this article, we initiate a matrix analysis of gain graphs by defining the adjacency matrices of gain graphs when the underlying group for labeling the edges is the multiplicative group of a field and characterize balance in such gain graphs using the characteristic polynomials. We also establish recurrence relations for the characteristic polynomials of a gain graph and discuss consequences of these relations. [Copyright &y& Elsevier]

Abstract: We develop linear representation theory for bicircular matroids, a chief example being a matroid associated with forests of a graph, and bicircular lift matroids, a chief example being a matroid associated with spanning forests. (These are bias and lift matroids of contrabalanced biased graphs.) The theory is expressed largely in terms of antivoltages (edge labellings that defy Kirchhoff''s voltage law) with values in the multiplicative or additive group of the scalar field. We emphasize antivoltages with values in cyclic groups and finite vector spaces since they are crucial for representing the matroids over finite fields; and integer-valued antivoltages with bounded breadth since they are crucial in constructions. We find bounds for the existence of antivoltages and we solve some examples. Other results: The number of antivoltages in an abelian group is a polynomial function of the group order, and the number of integral antivoltages with bounded breadth is a polynomial in the breadth bound. We conclude with an application to complex representation. There are many open questions. [Copyright &y& Elsevier]

A gain graph is a graph whose oriented edges are labelled invertibly from a group G, the gain group. A gain graph determines a biased graph and therefore has three natural matroids (as shown in Parts I and II): the bias matroid G has connected circuits; the complete lift matroid L0 and its restriction to the edge set, the lift matroid L, have circuits not necessarily connected. We investigate representations of these matroids. Each has a canonical vector representation over any skew field F such that G⊆F* (in the case of G) or G⊆F+ (in the case of L and L0). The representation of G is unique up to change of gains when the gain graph is full, but not in general. The representation of G or L is unique or semi-unique (up to changing the gains) for ‘thick’ biased graphs. The lift representations are unique (up to change of gains) for L0 but not for L. The bias matroid is representable also in other ways by points and hyperplanes; one of these representations dualizes the vector representation, while two, in projective space, strongly generalize the theorems of Menelaus and Ceva. (The latter specialize to properties of the geometry of midpoints and farpoints, and of median and edge-parallel hyperplanes, in an affine simplex.) The dual hyperplane representation can be abstracted away from fields to a kind of equational logic and permutation geometry that exist for every gain group. The lift matroids are representable by orthographic points and by linear, projective, and affinographic hyperplanes. L0 also has a metric hyperplanar representation that depends on the Pythagorean theorem. Incidental results are that Whitney''s 2-isomorphism operations preserve gains and, to an extent, matroids; and new definitions of the bias and lift matroids based on extremal properties of the rank functions. [Copyright &y& Elsevier]