Search

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.

Yuan, Shao and Liu proved that the H-shape tree H' n = P 1,n−6 1,2;n−3 minimizes the spectral radius among all graphs with order n ≥ 9 and diameter n−4. In this paper, we achieve the spectral characterization of all graphs in the set H' = {H' n}n ≥ 8. More precisely we show that H'n is determined by its spectrum if and only if n ≠ 8, 9, 12, and detect all cospectral mates of H' 8, H' 9 and H' 12. Divisibility between characteristic polynomials of graphs turns out to be an important tool to reach our goals. [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.

The index ≥1(1) of a signed graph 1= (G; -) is just the largest eigenvalue of its adjacency matrix. For any n > 4 we identify the signed graphs achieving the minimum index in the class of signed bicyclic graphs with n vertices. Apart from the n = 4 case, such graphs are obtained by considering a starlike tree with four branches of suitable length (i.e. four distinct paths joined at their end vertex u) with two additional negative independent edges pairwise joining the four vertices adjacent to u. As a by-product, all signed bicyclic graphs containing a theta-graph and whose index is less than 2 are detected. [ABSTRACT FROM AUTHOR]

Topological indices, i.e., numerical invariants suitably associated to graphs and only depending upon their isomorphism type, have important applications in Chemistry. Their computation constitutes an important branch of Chemical Graph Theory. In this paper, we focus on some degree and distance-based invariants related to the Zagreb indices, the Szeged index and the Wiener index, namely, the F-index, the vertex PI index and the hyper-Wiener index. In particular, we find the formulæ to compute these topological invariants for wreath product of graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph with order n and size m. For each real number α ∈ [ 0 , 1 ] , the A α -matrix of a graph G is defined as A α (G) := α D (G) + (1 − α) A (G) , where D (G) = d i a g (d 1 , ... , d n) is the degree matrix of G, and A (G) is its adjacency matrix. The functions s (G) = ∑ 1 ≤ i ≤ n d i − 2 m n a n d v a r (G) = 1 n ∑ 1 ≤ i ≤ n d i − 2 m n 2 have been already used elsewhere as measures of graph irregularity. In this paper, we find several bounds for the spectral radius λ (G) of the matrix A α (G). Especially, when G is non-empty we prove for α ∈ [ 0 , 1) that s 2 (G) 2 n 2 n (2 α − α 2) Δ 2 + 2 (1 − α) 2 m ≤ λ (G) − 2 m n ≤ 1 + (2 α − α 2) n Ω (G) 2 + (1 − α) 2 s (G) , where Ω (G) = Δ (G) − ⌈ 2 m / n ⌉ + 1 and Δ (G) is the maximum vertex degree of G. These inequalities extend to the A α -matrix a Nikiforov's result involving the spectral radius of the adjacency matrix. In addition, for fixed order and size, we determine the graphs minimizing the degree variance v a r (G) and compute the A α -spectrum of some blown-up graphs. [ABSTRACT FROM AUTHOR]

Let T be the multiplicative group of complex units, and let L(Φ) denote the Laplacian matrix of a nonempty T-gain graph Φ=(Γ,T,γ). The gain line graph L(Φ) and the gain subdivision graph S(Φ) are defined up to switching equivalence. We discuss how the eigenspaces determined by the adjacency eigenvalues of L(Φ) and S(Φ) are related with those of L(Φ). [ABSTRACT FROM AUTHOR]

A well-known fact in Spectral Graph Theory is the existence of pairs of cospectral (or isospectral) nonisomorphic graphs, known as PINGS. The work of A.J. Schwenk (in 1973) and of C. Godsil and B. McKay (in 1982) shed some light on the explanation of the presence of cospectral graphs, and they gave routines to construct PINGS. Here, we consider the Godsil–McKay-type routines developed for graphs, whose adjacency matrices are (0 , 1) -matrices, to the level of signed graphs, whose adjacency matrices allow the presence of − 1 s. We show that, with suitable adaption, such routines can be successfully ported to signed graphs, and we can build pairs of cospectral switching nonisomorphic signed graphs. [ABSTRACT FROM AUTHOR]