Search

A quaternion unit gain graph is a graph where each orientation of an edge is given a quaternion unit, which is the inverse of the quaternion unit assigned to the opposite orientation. In this paper we define the adjacency, Laplacian and incidence matrices for a quaternion unit gain graph and study their properties. These properties generalize several fundamental results from spectral graph theory of ordinary graphs, signed graphs and complex unit gain graphs. Bounds for both the left and right eigenvalues of the adjacency and Laplacian matrix are developed, and the right eigenvalues for the cycle and path graphs are explicitly calculated.

A complex unit gain graph ($\mathbb{T}$-gain graph), $\Phi = (G, \varphi)$ is a graph where the function $\varphi$ assigns a unit complex number to each orientation of an edge of $G$, and its inverse is assigned to the opposite orientation. A $ \mathbb{T} $-gain graph $\Phi$ is balanced if the product of the edge gains of each cycle (with a fixed orientation) is $1$. Signed graphs are special cases of $\mathbb{T}$-gain graphs. The adjacency matrix of $\Phi$, denoted by $ \mathbf{A}(\Phi)$ is defined canonically. The gain Laplacian for $\Phi$ is defined as $\mathbf{L}(\Phi) = \mathbf{D}(\Phi) - \mathbf{A}(\Phi)$, where $\mathbf{D}(\Phi)$ is the diagonal matrix with diagonal entries are the degrees of the vertices of $G$. The minimum number of vertices (resp., edges) to be deleted from $\Phi$ in order to get a balanced gain graph the frustration number (resp, frustration index). We show that frustration number and frustration index are bounded below by the smallest eigenvalue of $\mathbf{L}(\Phi)$. We provide several lower and upper bounds for extremal eigenvalues of $\mathbf{L}(\Phi)$ in terms of different graph parameters such as the number of edges, vertex degrees, and average $2$-degrees. The signed graphs are particular cases of the $\mathbb{T}$-gain graphs, all the bounds established in paper hold for signed graphs. Most of the bounds established here are new for signed graphs. Finally, we perform comparative analysis for all the obtained bounds in the paper with the state-of-the-art bounds available in the literature for randomly generated Erd\H{o}s-Re\'yni graphs. Some of the major highlights of our paper are the gain-dependent bounds, limit convergence of the bounds to the extremal eigenvalues, and optimal extremal bounds obtained by posing optimization problems to achieve the best possible bounds., Comment: Preliminary version. 32 pages

Dowling and Rhodes defined different lattices on the set of triples (Subset, Partition, Cross Section) over a fixed finite group G. Although the Rhodes lattice is not a geometric lattice, it defines a matroid in the sense of the theory of boolean representable simplicial complexes. This turns out to be the direct sum of a uniform matroid with the lift matroid of the complete gain link graph over G. As is well known, the Dowling lattice defines the frame matroid over a similar gain graph. This gives a new perspective on both matroids and also an application of matroid theory to the theory of finite semigroups. We also make progress on an important question for these classical matroids: what are the minimal boolean representations and the minimum degree of a boolean matrix representation?

Let $G$ be an arbitrary group. We define a gain-line graph for a gain graph $(\Gamma,\psi)$ through the choice of an incidence $G$-phase matrix inducing $\psi$. We prove that the switching equivalence class of the gain function on the line graph $L(\Gamma)$ does not change if one chooses a different $G$-phase inducing $\psi$ or a different representative of the switching equivalence class of $\psi$. 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 $\mathcal H_\Gamma$ of $G$-phases of $\Gamma$ allows us to characterize gain functions on $\Gamma$, gain functions on $L(\Gamma)$, 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., Comment: 28 pages, 6 figures, 1 table

Let Φ = ( G , φ ) be a T -gain graph with maximum degree Δ. Zhou et al. (2018) [35] gave a lower bound of the rank of simple graphs in items of maximum degree. Motivated by above result, in this paper, we extend this result to T -gain graphs. We obtain that r ( Φ ) ≥ n Δ for a T -gain graph. All the corresponding extremal graphs are characterized. Furthermore, we also obtain some other results about the rank of T -gain graphs.

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. In this paper, we characterize the structure of the complex unit gain graphs with exactly one positive eigenvalue. As its applications, we obtain the complex unit gain graphs with rank 2, and investigate the complex unit gain graphs with exactly two eigenvalues different from 0 and −1.

Let T be the group of all complex numbers z with | z | = 1 . A complex unit gain graph, or simply a T -gain graph, is a triple Φ = ( G , T , φ ) consisting of a graph G = ( V , E ) , the circle group T and a gain function φ : E → → T such that φ ( v i v j ) = φ ( v j v i ) − 1 = φ ( v j v i ) ‾ for any adjacent vertices v i and v j . The adjacency matrix A ( Φ ) of the T -gain graph Φ = ( G , T , φ ) of order n is an n × n complex matrix ( a i j ) , where a i j = a j i ‾ = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 if otherwise. The rank of a T -gain graph Φ, denoted by r ( Φ ) , is the rank of the adjacency matrix of Φ. Yu et al. [24] obtained some properties of inertia indexes of a T -gain graph and they characterized the T -gain unicyclic graphs with small positive or negative index. Lu [8] characterized the T -gain bicyclic graphs with rank 2 , 3 or 4. Motivated by above, we determine the rank of a T -gain unicyclic graph and classify the T -gain graphs with rank 2.

Let G ϕ be an n-vertex complex unit gain graph and let G be its underlying graph. The adjacency rank of G ϕ , written as r ( G ϕ ) , is the rank of its adjacency matrix and denote by α ′ ( G ) the ...

A T -gain graph is a triple Φ = ( G , T , ϕ ) consisting of an underlying graph G = ( V ( G ) , E ( G ) ) , the circle group T = { z ∈ C : | z | = 1 } and a gain function ϕ : E → → T , such that ϕ ...

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(\mathbb 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 $\mathbb C G$ to the algebra $M_n(\mathbb C G)$. We prove that a gain graph is balanced if and only if the spectrum of the represented adjacency matrix associated with any (or equivalently all) faithful unitary representation of $G$ 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 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., Comment: 27 pages, 3 tables, 5 figures. In this second version, the word "balancedness" (with the meaning of "property of being balanced") has been replaced by the word "balance" both in the title and in the body of the article

A complex unit gain graph (or T -gain graph) is a triple Φ = ( G , T , φ ) (or ( G , φ ) for short) consisting of a simple graph G, as the underlying graph of ( G , φ ) , the set of unit complex numbers T = { z ∈ C : | z | = 1 } and a gain function φ : E → → T with the property that φ ( e i , j ) = φ ( e j , i ) − 1 . In this paper, we prove that 2 m ( G ) − 2 c ( G ) ≤ r ( G , φ ) ≤ 2 m ( G ) + c ( G ) , where r ( G , φ ) , m ( G ) and c ( G ) are the rank of the Hermitian adjacency matrix H ( G , φ ) , the matching number and the cyclomatic number of G, respectively. Furthermore, the complex unit gain graphs ( G , T , φ ) with r ( G , φ ) = 2 m ( G ) − 2 c ( G ) and r ( G , φ ) = 2 m ( G ) + c ( G ) are characterized. These results generalize the corresponding known results about undirected graphs, mixed graphs and signed graphs. Moreover, we show that 2 m ( G − V 0 ) ≤ r ( G , φ ) ≤ 2 m ( G ) + S holds for any S ⊂ V ( G ) such that G − S is bipartite and any subset V 0 of V ( G ) such that G − V 0 is acyclic.

A complex unit gain graph (or $\mathbb{T}$-gain graph) is a triple $\Phi=(G, \mathbb{T}, \varphi)$ ($(G, \varphi)$ for short) consisting of a graph $G$ as the underlying graph of $(G, \varphi)$, $\mathbb{T}= \{ z \in C:|z|=1 \} $ is a subgroup of the multiplicative group of all nonzero complex numbers $\mathbb{C}^{\times}$ and a gain function $\varphi: \overrightarrow{E} \rightarrow \mathbb{T}$ such that $\varphi(e_{ij})=\varphi(e_{ji})^{-1}=\overline{\varphi(e_{ji})}$. In this paper, we investigate the relation among the rank, the independence number and the cyclomatic number of a complex unit gain graph $(G, \varphi)$ with order $n$, and prove that $2n-2c(G) \leq r(G, \varphi)+2\alpha(G) \leq 2n$. Where $r(G, \varphi)$, $\alpha(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $A(G, \varphi)$, the independence number and the cyclomatic number of $G$, respectively. Furthermore, the properties of the complex unit gain graph that reaching the lower bound are characterized., Comment: arXiv admin note: substantial text overlap with arXiv:1907.07837, arXiv:1909.07555

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.

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 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 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., Comment: 14 pages, 2 figures

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 ( u , v ) of weight w is as good as the presence of the edge ( v , u ) with weight w ¯ , the complex conjugate of w . Let G be a weighted directed graph on vertices 1 , 2 , … , n . Denote by w u v the weight of an edge ( u , v ) ∈ E ( G ) . The adjacency matrix A ( G ) of G is an n × n matrix with entries a i j = w i j or w ¯ j i or 0, depending on whether ( i , j ) ∈ E ( G ) or ( j , i ) ∈ E ( G ) or otherwise, respectively. We supply a characterization of those unicyclic weighted directed graphs G whose edges have weights from the set { ± 1 , ± i } and whose adjacency matrix A ( G ) satisfies the following property: ‘ λ is an eigenvalue of A ( G ) with multiplicity k if and only if 1 / λ is an eigenvalue of A ( G ) with the same multiplicity’.

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 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.

Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching is an operation that transforms one skew gain graph into another, driven by a selector that selects an element of some group Γ in each of its vertices. In this paper, we investigate a generalization of this model, in which we insist that in each vertex v the selected elements are taken from a subgroup Γv of Γ. We call this operation subgroup switching. Our main interest in this paper is in establishing which properties of the theory of switching classes of the skew gain graphs carry over to subgroup switching classes, and which do not.

A $\mathbb{T}$-gain graph is a triple $\Phi=(G,\mathbb{T},\varphi)$ consisting of a graph $G=(V,E)$, the circle group $\mathbb{T}=\{z\in C: |z|=1\}$ and a gain function $\varphi:\overrightarrow{E}\rightarrow \mathbb{T}$ such that $\varphi(e_{ij})=\varphi(e_{ji})^{-1}=\overline{\varphi(e_{ji})}$. The rank of $\mathbb{T}$-gain graph $\Phi$, denoted by $r(\Phi)$, is the rank of the adjacency matrix of $\Phi$. In 2015, Yu, Qu and Tu [ G. H. Yu, H. Qu, J. H. Tu, Inertia of complex unit gain graphs, Appl. Math. Comput. 265(2015) 619--629 ] obtained some properties of inertia of a $\mathbb{T}$-gain graph. They characterized the $\mathbb{T}$-gain unicyclic graphs with small positive or negative index. Motivated by above, in this paper, we characterize the complex unit gain bicyclic graphs with rank 2, 3 or 4., Comment: 15 pages, 4 figures

We study new posetsQ obtained by removing from a geometric latticeL of a biased graph certain flats indexed by a simplicial complex C. (One example ofL is the lattice of flats of the vector matroid of a root systemBn.) We study the structure and compute the characteristic polynomial ofQ. With certain choices ofL and C, including ones for whichQ is a lattice interpolating between those ofBn andDn, we observe curious relationships among the roots of the characteristic polynomials of Q;L ,a ndC. Mathematics Subject Classifications ( 1991): Primary 06A07; Secondary 05C15, 05B35, 05C99, 52B30.

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., Comment: 13 pages, 1 figure, to appear in Linear Algebra Appl