On the Aα-spectral radius of a graph Xue, Jie; Lin, Huiqiu; Liu, Shuting ...
Linear algebra and its applications,
08/2018, Letnik:
550
Journal Article
Recenzirano
Let G be a graph with adjacency matrix A(G) and let D(G) be the diagonal matrix of the degrees of G. For any real α∈0,1, Nikiforov 3 defined the matrix Aα(G) asAα(G)=αD(G)+(1−α)A(G). The largest ...eigenvalue of Aα(G) is called the Aα-spectral radius of G. In this paper, we give three edge graft transformations on Aα-spectral radius. As applications, we determine the unique graph with maximum Aα-spectral radius among all connected graphs with diameter d, and determine the unique graph with minimum Aα-spectral radius among all connected graphs with given clique number. In addition, some bounds on the Aα-spectral radius are obtained.
The goal of this article is to display a Q-polynomial structure for the Attenuated Space poset Aq(N,M). The poset Aq(N,M) is briefly described as follows. Start with an (N+M)-dimensional vector space ...H over a finite field with q elements. Fix an M-dimensional subspace h of H. The vertex set X of Aq(N,M) consists of the subspaces of H that have zero intersection with h. The partial order on X is the inclusion relation. The Q-polynomial structure involves two matrices A,A⁎∈MatX(C) with the following entries. For y,z∈X the matrix A has (y,z)-entry 1 (if y covers z); qdimy (if z covers y); and 0 (if neither of y,z covers the other). The matrix A⁎ is diagonal, with (y,y)-entry q−dimy for all y∈X. By construction, A⁎ has N+1 eigenspaces. By construction, A acts on these eigenspaces in a (block) tridiagonal fashion. We show that A is diagonalizable, with 2N+1 eigenspaces. We show that A⁎ acts on these eigenspaces in a (block) tridiagonal fashion. Using this action, we show that A is Q-polynomial. We show that A,A⁎ satisfy a pair of relations called the tridiagonal relations. We consider the subalgebra T of MatX(C) generated by A,A⁎. We show that A,A⁎ act on each irreducible T-module as a Leonard pair.
Let G˙ be an unbalanced signed graph. In this paper, we establish that e(G˙)⩽12(n2−n)−(n−3) and ρ(G˙)⩽n−2 if G˙ does not contain unbalanced K4 as a signed subgraph. Moreover, comprehensive ...characterizations of the extremal signed graphs have been obtained.
•The situation that the index of signed graph equals to the spectral radius of underlying graph has been characterized.•We determine the Turán number of K4− in unbalanced signed graph, and we characterize all the extremal signed graphs.•We solve the spectral Turán problem among all K4−-free unbalanced signed graphs.
Many problems in real world, either natural or man-made, can be usefully represented by graphs or networks. Along with a complex topological structure, the weight is a vital factor in characterizing ...some properties of real networks. In this paper, we define a class of the weighted edge corona product networks. The generalized adjacency (resp., Laplacian and signless Laplacian) spectra with two different structures are determined. As applications, the number of spanning trees and Kirchhoff index of the weighted edge corona product networks are computed.
•We first define a class of the weighted edge corona product networks.•Three types of spectra for that networks are given.•The number of spanning trees and Kirchhoff index of that networks are determined.
In this note we show that for each positive integer a⩾2 there exist infinitely many trees whose spectral radius is equal to 2a. Such trees are obtained by replacing the central edge of the double ...star S(a,2a−2) with suitable bidegreed caterpillars.
A complex adjacency matrix of a mixed graph is introduced in the present paper, which is a Hermitian matrix and called the Hermitian-adjacency matrix. It incorporates both adjacency matrix of an ...undirected graph and skew-adjacency matrix of an oriented graph. Some of its properties are studied. Furthermore, properties of its characteristic polynomial are studied. Cospectral problems among mixed graphs, including mixed graphs and their underlying graphs, oriented graphs and their underlying graphs, are studied. We give equivalent conditions for a mixed graph (especially oriented graph) that share the same spectrum with its underlying graph. As a consequence, we reconfirm a conjecture which was proposed by Cui and Hou in Ref. 8. We also show that the spectrum of the Hermitian matrix of a mixed graph is invariant when changing the value of any its cut edge (if any).
Correspondingly, an energy of a mixed graph is introduced and called the Hermitian energy. It incorporates both the energy of an undirected graph and the skew energy of an oriented graph. Some of its bounds are given. Especially, the mixed graphs with optimal upper bound of Hermitian energy are characterized. An infinite family of mixed graphs attaining the maximum Hermitian energy is constructed. Moreover, the Hermitian energy of a mixed tree is showed to be equal to the energy of its underlying tree. Finally, the integral formula for Hermitian energy of a mixed graph is given.
On the Aα-spectra of trees Nikiforov, Vladimir; Pastén, Germain; Rojo, Oscar ...
Linear algebra and its applications,
05/2017, Letnik:
520
Journal Article
Recenzirano
Let G be a graph with adjacency matrix A(G) and let D(G) be the diagonal matrix of the degrees of G. For every real α∈0,1, define the matrix Aα(G) asAα(G)=αD(G)+(1−α)A(G).
This paper gives several ...results about the Aα-matrices of trees. In particular, it is shown that if TΔ is a tree of maximal degree Δ, then the spectral radius of Aα(TΔ) satisfies the tight inequalityρ(Aα(TΔ))<αΔ+2(1−α)Δ−1, which implies previous bounds of Godsil, Lovász, and Stevanović. The proof is deduced from some new results about the Aα-matrices of Bethe trees and generalized Bethe trees.
In addition, several bounds on the spectral radius of Aα of general graphs are proved, implying tight bounds for paths and Bethe trees.
Let G be a graph with adjacency matrix A(G), and let D(G) be the
diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is
defined as Q(G):= A(G) +D(G). Cvetkovic called the study of ...the adjacency
matrix the A-spectral theory, and the study of the signless Laplacian{the
Q-spectral theory. To track the gradual change of A(G) into Q(G), in this
paper it is suggested to study the convex linear combinations A_ (G) of A(G)
and D(G) defined by A? (G) := ?D(G) + (1 - ?)A(G), 0 ? ? ? 1. This study
sheds new light on A(G) and Q(G), and yields, in particular, a novel
spectral Tur?n theorem. A number of open problems are discussed.
nema
We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence ...of good 2-lifts of every graph. We also establish the existence of infinite families of "irregular Ramanujan" graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all nontrivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$ for all c, d ≥ 3. Our proof exploits a new technique for controlling the eigenvalues of certain random matrices, which we call the "method of interlacing polynomials."
PDF
