Search

Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively. For any real α ∈ [0, 1], we consider Aα (G) = αD(G) + (1 − α)A(G) as a graph matrix, whose largest eigenvalue is called the Aα -spectral radius of G. We first show that the smallest limit point for the Aα -spectral radius of graphs is 2, and then we characterize the connected graphs whose Aα -spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their Aα -spectra.

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 (Φ).

For a graph G containing no component isomorphic to the 2-vertex path graph, the augmented Zagreb index (AZI) of G is defined as AZI(G)=∑uv∈E(G)([Formula presented])3.This topological index has been proved to be closely correlated with the formation heat of heptanes and octanes. A k-apex tree is a connected graph G admitting a k-subset of vertices X such that G−X is a tree, but for any subset of vertices X′ of order less than k, G−X′ is not a tree. In this paper, we determine the minimum AZI among all k-apex trees for k∈{1,2,3}.

A signed graph is a pair Γ = (G; ), where x = (V (G);E(G)) is a graph and E(G) -> {+1;−1} is the sign function on the edges of G. For any > [0; 1] we consider the matrix Aα(Γ) = αD(G) + (1 −α )A(Γ); where D(G) is the diagonal matrix of the vertex degrees of G, and A(Γ) is the adjacency matrix of Γ. Let mAα(Γ) be the multiplicity of α as an A(Γ)-eigenvalue, and let G have p(G) pendant vertices, q(G) quasi-pendant vertices, and no components isomorphic to K2. It is proved that mA(Γ)() = p(G) − q(G) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that mA(Γ)() = p(G) − q(G) +mN(Γ)(); where mN(Γ)() denotes the multiplicity of as an eigenvalue of the matrix N(Γ) obtained from A(Γ) taking the entries corresponding to the internal vertices which are not quasipendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L(Γ) = D(G) − A(Γ). Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A(Γ)-eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass Gœ ` G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars.

We describe the Italy-South Africa Research Program 2018–2020, focusing on the mobility scheme “Algebraic Graph Theory and Complex Networks” which supported a series of scientific initiatives between the University of Cape Town (Cape Town, South Africa) and the University of Naples Federico II (Naples, Italy) during the years 2018–2021. We sketch the relevant steps of the collaboration, focusing on the creation of a network of researchers between Italy and South Africa in the fields of Graph Theory and Combinatorics. In this context it becomes more relevant the role of the “Workshop on Graphs, Topology and Topological Groups 2021” and of the corresponding proceedings.

Hoffman and Smith proved that in a graph with maximum degree Δ if all edges are subdivided infinitely many times, then the largest eigenvalue, also called index, of the adjacency matrix converges to Δ/(Δ-1). For the (signless) Laplacian of graphs, a similar result holds and the limit value is its square Δ 2/ (Δ - 1). Throughout the years, several scholars have progressed into characterizing the (connected) graphs whose adjacency or (signless) Laplacian index does not exceed the Hoffman–Smith limit value for Δ = 3 , still there is not a complete characterization of such graphs. Here, we consider the signless Laplacian variant of this problem, and we characterize a large portion of such graphs. Also, we provide a structural restriction for the graphs not yet included for the complete characterization. Finally, we discuss the consequences on the adjacency variant of this problem.

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.

In this paper we describe two methods, both inspired from Godsil-McKay switching on simple graphs, to build cospectral gain graphs whose gain group consists of the complex numbers of modulus 1 (the circle group). The results obtained here can be also applied to the Hermitian matrix of mixed graphs.

Signed graphs are graphs whose edges get signs ±1 and, as for unsigned graphs, they can be studied by means of graph matrices. Here we focus our attention to the largest eigenvalue, also known as the index of the adjacency matrix of signed graphs. Firstly we give some general results on the index variation when the corresponding signed graph is perturbed. Also, we determine signed graphs achieving the minimal or the maximal index in the class of unbalanced unicyclic graphs of order n ≥ 3 .

A signed graph Γ is a graph whose edges are labeled by signs. If Γ has n vertices, its spectral radius is the number ϱ(Γ):= max{∣λi(Γ)∣: 1 ⩽ i ⩽ n}, where λ1(Γ) ⩾ … ⩾ λn(Γ) are the eigenvalues of the signed adjacency matrix A(Γ). Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes $$\mathfrak{U}{_n}$$ and $$\mathfrak{B}{_n}$$ of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.

A signed graph is a pair Γ = ( G , σ ) , where G is a graph, and σ : E ( G ) ⟶ { + 1 , − 1 } is a signature of the edges of G . A signed graph Γ is said to be unbalanced if there exists a cycle in Γ with an odd number of negatively signed edges. In this paper it is presented a linear time algorithm which computes the inertia indices of an unbalanced unicyclic signed graph. Additionally, the algorithm computes the number of eigenvalues in a given real interval by operating directly on the graph, so that the adjacency matrix is not needed explicitly. As an application, the algorithm is employed to check the integrality of some infinite families of unbalanced unicyclic graphs. In particular, the multiplicities of eigenvalues of signed circular caterpillars are studied, getting a geometric characterization of those which are non-singular and sufficient conditions for them to be non-integral. Finally, the algorithm is also used to retrieve the spectrum of bidegreed signed circular caterpillars, none of which turns out to be integral.

Let $\mathbb T$ be the multiplicative group of complex units, and let $\mathcal L (\Phi)$ denote a line graph of a $\mathbb{T}$-gain graph $\Phi$. Similarly to what happens in the context of signed graphs, the real number $\min Spec(A(\mathcal L (\Phi))$, that is, the smallest eigenvalue of the adjacency matrix of $\mathcal L(\Phi)$, is not less than $-2$. The structural conditions on $\Phi$ ensuring that $\min Spec(A(\mathcal L (\Phi))=-2$ are identified. When such conditions are fulfilled, bases of the $-2$-eigenspace are constructed with the aid of the star complement technique.

Let T 4 = { &plusmn, 1 , &plusmn, i } be the subgroup of fourth roots of unity inside T , the multiplicative group of complex units. For a T 4 -gain graph &Phi, = ( &Gamma, T 4 , &phi, ) , we introduce gain functions on its line graph L ( &Gamma, ) and on its subdivision graph S ( &Gamma, ) . The corresponding gain graphs L ( &Phi, ) and S ( &Phi, ) are defined up to switching equivalence and generalize the analogous constructions for signed graphs. We discuss some spectral properties of these graphs and in particular we establish the relationship between the Laplacian characteristic polynomial of a gain graph &Phi, and the adjacency characteristic polynomials of L ( &Phi, ) . A suitably defined incidence matrix for T 4 -gain graphs plays an important role in this context.

A well--known fact in Spectral Graph Theory is the existence of pairs of 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 isospectral 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., Comment: 13 pages, 4 figures