Search

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 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]

For a (simple) graph H and non-negative integers c0, c1, . . ., cd (cd ≠ 0), p(H) = Pd ...k=0 ck · Hk is the lexicographic polynomial in H of degree d, where the sum of two graphs is their join and ck · Hk is the join of ck copies of Hk. The graph Hk is the kth power of H with respect to the lexicographic product (H0 = K1). The spectrum (if H is connected and regular) and the Laplacian spectrum (in general case) of p(H) are determined in terms of the spectrum of H and ck's. Constructions of infinite families of cospectral or integral graphs are announced. [ABSTRACT FROM AUTHOR]

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). Cvetković 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 byAα (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. [ABSTRACT FROM AUTHOR]

Abstract: Methods of enumeration of spanning trees in a finite graph, a problem related to various areas of mathematics and physics, have been investigated by many mathematicians and physicists. A graph G is said to be n-rotational symmetric if the cyclic group of order n is a subgroup of the automorphism group of G. Some recent studies on the enumeration of spanning trees and the calculation of their asymptotic growth constants on regular lattices with toroidal boundary condition were carried out by physicists. A natural question is to consider the problem of enumeration of spanning trees of lattices with cylindrical boundary condition, which are the so-called rotational symmetric graphs. Suppose G is a graph of order N with n-rotational symmetry and all orbits have size n, which has n isomorphic induced subgraphs . In this paper, we prove that if there exists no edge between and for , then the number of spanning trees of G can be expressed in terms of the product of the weighted enumerations of spanning trees of n graphs ''s for , where has vertices if and vertices otherwise. As applications we obtain explicit expressions for the numbers of spanning trees and asymptotic tree number entropies for five lattices with cylindrical boundary condition in the context of physics. [Copyright &y& Elsevier]

Abstract: The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G. [ABSTRACT FROM AUTHOR]

Abstract: A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency/Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence. [Copyright &y& Elsevier]

Abstract: A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix which is in a prescribed way defined for any graph. This theory is called -theory. We outline a spectral theory of graphs based on the signless Laplacians and compare it with other spectral theories, in particular to those based on the adjacency matrix and the Laplacian . As demonstrated in the first part, the -theory can be constructed in part using various connections to other theories: equivalency with -theory and -theory for regular graphs, common features with -theory for bipartite graphs, general analogies with -theory and analogies with -theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles. [Copyright &y& Elsevier]

Abstract: For , , a Bethe tree is a rooted tree with levels which the root vertex has degree , the vertices from level to have degree and the vertices at the level are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees. [Copyright &y& Elsevier]

Abstract: We find the characteristic polynomials of adjacency and Laplacian matrices of arbitrary unweighted rooted trees in term of vertex degrees, using the concept of the rooted product of graphs. Our result generalizes a result of Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97–117] on a special class of rooted unweighted trees, namely the trees such that their vertices in the same level have equal degrees. [Copyright &y& Elsevier]

Abstract: A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let be any connected graph. Let be the graph obtained from by attaching a generalized Bethe tree , by its root, to each vertex of . We characterize completely the eigenvalues of the signless Laplacian, Laplacian and adjacency matrices of the graph including results on the eigenvalue multiplicities. Finally, for the Laplacian and signless Laplacian matrices, we recall a procedure to compute a tight upper bound on the algebraic connectivity of as well as on the smallest eigenvalue of the signless Laplacian matrix of whenever is a non-bipartite graph. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on some operations of graphs and give a kind of eigenvalue interlacing in terms of the adjacency matrix, standard Laplacian, and normalized Laplacian. Also, we explore some applications of this interlacing. [Copyright &y& Elsevier]

A generalized Bethe tree is a rooted tree for which the vertices in each level having equal degree. Let Bk be a generalized BETHE tree of k level, and let Tr be a connected transitive graph on r vertices. Then we obtain a graph BkoTr from r copies of Bk and Tr by appending r roots to the vertices of Tr respectively. In this paper, we give a simple way to characterize the eigenvalues of the adjacency matrix A(BkoTr) and the Laplacian matrix L(BkoTr) of BkoTr by means of symmetric tridiagonal matrices of order k. We also present some structure properties of the Perron vectors of A(BkoTr) and the Fiedler vectors of L(BkoTr). In addition, we obtain some results on transitive graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n k−j+1 and d k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of for the case of two vertices in level 1 (n k =2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2⩽ j ⩽ k, while the diagonal entries are 0,…,0,±1, in the case of the adjacency matrix, and d 1, d 2,…, d k−1, d k ±1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree. [Copyright &y& Elsevier]