Search

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]

Graph coarsening is a widely used dimensionality reduction technique for approaching large-scale graph machine-learning problems. Given a large graph, graph coarsening aims to learn a smaller-tractable graph while preserving the properties of the originally given graph. Graph data consist of node features and graph matrix (e.g., adjacency and Laplacian). The existing graph coarsening methods ignore the node features and rely solely on a graph matrix to simplify graphs. In this paper, we introduce a novel optimization-based framework for graph dimensionality reduction. The proposed framework lies in the unification of graph learning and dimensionality reduction. It takes both the graph matrix and the node features as the input and learns the coarsen graph matrix and the coarsen feature matrix jointly while ensuring desired properties. The proposed optimization formulation is a multi-block non-convex optimization problem, which is solved efficiently by leveraging block majorization-minimization, log determinant, Dirichlet energy, and regularization frameworks. The proposed algorithms are provably convergent and practically amenable to numerous tasks. It is also established that the learned coarsened graph is ϵ 2 (0, 1) similar to the original graph. Extensive experiments elucidate the efficacy of the proposed framework for real-world applications. The code for all the experimental results is available at CODE. [ABSTRACT FROM AUTHOR]

Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph were obtained and discussed. [ABSTRACT FROM AUTHOR]

A Hamiltonian graph G is said to be hyper-Hamiltonian when G − v is Hamiltonian for any vertex v of G. In this paper, sufficient conditions for a graph to be hyper-Hamiltonian based on different parameters, such as degree and number of edges, are presented. Furthermore, other sufficient conditions for hyper-Hamiltonicity are obtained from spectral parameters, such as the spectral radii of the adjacency matrix, the signless Laplacian matrix and the distance matrix. Results on hyper-Hamiltonicity of a threshold graph through the eigenvalues of its Laplacian matrix are also presented. [ABSTRACT FROM AUTHOR]

Graph learning from data is a canonical problem that has received substantial attention in the literature. Learning a structured graph is essential for interpretability and identification of the relationships among data. In general, learning a graph with a specific structure is an NP-hard combinatorial problem and thus designing a general tractable algorithm is challenging. Some useful structured graphs include connected, sparse, multi-component, bipartite, and regular graphs. In this paper, we introduce a unified framework for structured graph learning that combines Gaussian graphical model and spectral graph theory. We propose to convert combinatorial structural constraints into spectral constraints on graph matrices and develop an optimization framework based on block majorization-minimization to solve structured graph learning problem. The proposed algorithms are provably convergent and practically amenable for a number of graph based applications such as data clustering. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. An open source R package containing the code for all the experiments is available at https://CRAN.R-project.org/package=spectralGraphTopology. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph. Let 0 ≤ α ≤ 1 . Let A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) where D ( G ) and A ( G ) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G , respectively. Let p ( G ) > 0 and q ( G ) be the number of pendant vertices and quasi-pendant vertices of G , respectively. Let m G ( α ) be the multiplicity of α as an eigenvalue of A α ( G ) . It is proved that m G ( α ) ≥ p ( G ) − q ( G ) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equality m G ( α ) = p ( G ) − q ( G ) + m N ( α ) is determined in which m N ( α ) is the multiplicity of α as an eigenvalue of the matrix N . This matrix is obtained from A α ( G ) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of A α ( G ) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given. [ABSTRACT FROM AUTHOR]

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [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 signed graph, where G is the underlying simple graph and σ : E ( G ) → { + , − } is the sign function on the edges of G . In this paper we consider the spectral characterization problem extended to the adjacency matrix and Laplacian matrix of signed graphs. After giving some basic results, we study the spectral determination of signed lollipop graphs, and we show that any signed lollipop graph is determined by the spectrum of its Laplacian matrix. [ABSTRACT FROM AUTHOR]

A complete caterpillar is a caterpillar in which each internal vertex is a quasi-pendent vertex. In this paper, in the class of all complete caterpillars on n vertices and diameter d, the caterpillar attaining the largest Laplacian index is determined. In addition, it is proved that this caterpillar also attains the largest adjacency index. [ABSTRACT FROM AUTHOR]

Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

Abstract: A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. For let be a generalized Bethe tree of levels and let such that (1) the edges of connecting vertices at consecutive levels have the same weight, and (2) for , each set of children of at the level defines a clique in which the edges have weight For let be the graph obtained from and the cliques at the levels for all Let be the graph obtained from the graphs joined at their respective roots. We give a complete characterization of the eigenvalues, including their multiplicities, of the Laplacian, signless Laplacian and adjacency matrices of the graph . Finally, we characterize the normalized Laplacian eigenvalues when is an unweighted graph. [Copyright &y& Elsevier]

We derive an upper bound on the largest signless Laplacian eigenvalue of an odd unicyclic graph. The bound is given in terms of the largest vertex degree and the largest height of the trees obtained removing the edges of the unique cycle in the graph. [ABSTRACT FROM AUTHOR]

Abstract: We characterize the eigenvalues and energy of the line graph whenever is (i) a generalized Bethe tree, (ii) a Bethe tree, (iii) a tree defined by generalized Bethe trees attached to a path, (iv) a tree defined by generalized Bethe trees having a common root, (v) a graph defined by copies of a generalized Bethe tree attached to a cycle and (vi) a graph defined by copies of a star attached to a cycle; in this case, explicit formulas for the eigenvalues and energy of are derived. [Copyright &y& Elsevier]

Abstract: Consider a graph on vertices with adjacency matrix and degree sequence . A universal adjacency matrix of is any matrix in Span with a nonzero coefficient for , where and and are the identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur. [Copyright &y& Elsevier]

Abstract: Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property. [Copyright &y& Elsevier]

Abstract: The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of . A caterpillar is a tree in which the removal of all pendant vertices makes it a path. Let and . Let with such thatLet be the caterpillar obtained from the stars and the path by identifying the root of with the -vertex of . The line graph of , denoted by , becomes a sequence of cliques , in this order, such that two consecutive cliques have in common exactly one vertex. In this paper, we characterize the eigenvalues and the energy of . Explicit formulas are given for the eigenvalues and the energy of where . Finally, a lower bound and an upper bound for the energy of are derived. [Copyright &y& Elsevier]

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: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [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: The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which [(1)] the edges connecting vertices at consecutive levels have the same weight, [(2)] each set of children, in one or more levels, defines a weighted clique, and [(3)] cliques at the same level are isomorphic. These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied. [ABSTRACT FROM AUTHOR]

Abstract: A Bethe tree of levels, , is a rooted tree such that the root vertex has degree , the vertices from level to have degree and the vertices at level are leaves. In this paper, we obtain a recurrence relation for the characteristic polynomial and the Laplacian characteristic polynomial of Bethe trees. As an application, we prove that there are no integral Bethe trees except for the star , and we obtain a recurrence relation for the Laplacian-energy-like invariant of Bethe trees. [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]

Several matrices can be associated to a graph such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question "Which graphs are determined by their spectrum?" remains a difficult problem in algebraic graph theory. In this article we enlarge the known families of graphs determined by their spectrum by considering some unicyclic graphs. An odd (resp. even) sun is a graph obtained by appending a pendant vertex to each vertex of an odd (resp. even) cycle. A broken sun is a graph obtained by deleting pendant vertices of a sun. In this paper we prove that a sun is determined by its Laplacian spectrum, an odd sun is determined by its adjacency spectrum (counter-examples are given for even suns) and we give some spectral characterizations of broken suns. [ABSTRACT FROM AUTHOR]

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: A generalized Bethe tree is a rooted tree in which vertices at the same distance from the root have the same degree. Let be a path of m vertices. Let be a set of generalized Bethe trees. Let be the tree obtained from and the trees by identifying the root vertex of with the vertex of . We give a complete characterization of the eigenvalues of the Laplacian and adjacency matrices of . In particular, we characterize their spectral radii and the algebraic conectivity. Moreover, we derive results concerning their multiplicities. Finally, we apply the results to the case . [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: A generalized Bethe tree is a rooted tree in which vertices at the same distance from the root have the same degree. Let be a set of trees such that, for [(1)] is a generalized Bethe tree of levels, [(2)] the vertices of at the level j have degree for , and [(3)] the edges of joining the vertices at the level j with the vertices at the level have weight for . Let be the tree obtained from the union of the trees joined at their respective root vertices. We give a complete characterization of the eigenvalues of the Laplacian and adjacency matrices of . Moreover, we derive results concerning their multiplicities. In particular, we characterize the spectral radii, the algebraic conectivity and the second largest Laplacian eigenvalue. [Copyright &y& Elsevier]

Abstract: Let G be a weighted rooted graph of k levels such that, for [(1)] each vertex at level j is adjacent to one vertex at level and all edges joining a vertex at level j with a vertex at level have the same weight, where the weight is a positive real number; [(2)] if two vertices at level j are adjacent then they are adjacent to the same vertex at level and all edges joining two vertices at level j have the same weight; [(3)] two vertices at level j have the same degree; [(4)] there is not a vertex at level j adjacent to others two vertices at the same level; We give a complete characterization of the eigenvalues of the Laplacian matrix and adjacency matrix of G. They are the eigenvalues of leading principal submatrices of two nonnegative symmetric tridiagonal matrices of order and the roots of some polynomials related with the characteristic polynomial of the referred submatrices. By application of the above mentioned results, we derive an upper bound on the largest eigenvalue of a graph defined by a weighted tree and a weighted triangle attached, by one of its vertices, to a pendant vertex of the tree. [Copyright &y& Elsevier]

Abstract: Let G be an n-vertex () simple graph embeddable on a surface of Euler genus (the number of crosscaps plus twice the number of handles). Denote by the maximum degree of G. In this paper, we first present two upper bounds on the Laplacian spectral radius of G as follows: [(i)] [(ii)] if G is 4-connected and either the surface is the sphere or the embedding is 4-representative, then Some upper bounds on the Laplacian spectral radius of the outerplanar and Halin graphs are also given. [Copyright &y& Elsevier]

Abstract: Let be a unicyclic simple undirected graph with largest vertex degree Δ. Let be the unique cycle of . The graph is a forest of r rooted trees with root vertices , respectively. Letwhere is the distance from v to u. Let and be the spectral radius of the Laplacian matrix and adjacency matrix of , respectively. We prove thatwhenever andwhenever or whenever and . [Copyright &y& Elsevier]

Abstract: A Bethe tree is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j have degree equal to and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of . Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of . Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree . These upper bounds are given in terms of the largest vertex degree and the radius of , and they are attained if and only if is a Bethe tree. [Copyright &y& Elsevier]

Abstract: Let G be a simple graph. Let and denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let denote the largest vertex degree. If G has just one cycle, thenThe equality holds if and only if . AndThe equality holds if and only if , n is even. [Copyright &y& Elsevier]

Abstract: We generalize the concept of a Bethe tree as follows: we say that an unweighted rooted tree is a generalized Bethe tree if in each level the vertices have equal degree. If is a generalized Bethe tree of k levels then we characterize completely the eigenvalues of the adjacency matrix and Laplacian matrix of a graph obtained from the union of r copies of and the cycle connecting the r vertex roots. Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. [Copyright &y& Elsevier]

Abstract: Let be a weighted rooted tree of k levels such that [(1)] the vertices in level j have a degree equal to d k−j+1 for j =1,2,…, k, and [(2)] the edges joining the vertices in level j with the vertices in level (j +1) have a weight equal to w k−j for j =1,2,…, k−1. We give a complete characterization of the eigenvalues of the Laplacian matrix and adjacency matrix of . They are the eigenvalues of leading principal submatrices of two nonnegative symmetric tridiagonal matrices of order k × k. Moreover, we give some results concerning their multiplicities. By application of the above mentioned results, we derive upper bounds on the largest eigenvalue of any weighted tree and the spectra of some weighted Bethe trees. [Copyright &y& Elsevier]

Abstract: The higher Randić index R t (G) of a simple graph G is defined aswhere δ i denotes the degree of the vertex i and i 1 i 2⋯i t+1 runs over all paths of length t in G. In [J.A. Rodríguez, A spectral approach to the Randić index, Linear Algebra Appl. 400 (2005) 339–344], the lower and upper bound on R 1(G) was determined in terms of a kind of Laplacian spectra, and the lower and upper bound on R 2(G) were done in terms of kinds of adjacency and Laplacian spectra. In this paper we characterize the graphs which achieve the upper or lower bounds of R 1(G) and R 2(G), respectively. [Copyright &y& Elsevier]

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]

Abstract: Let be an unweighted tree with vertex root v which is the union of two trees , such that V 1 ∩ V 2 ={v} and and have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of . They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed. [Copyright &y& Elsevier]

Abstract: Let be a tree with vertex set V. Let d v denotes the degree of v ∈ V. Let Δ =max{d v : v ∈ V}. Let u ∈ V such that d u = Δ. Let k = e u +1 where e u is the excentricity of u. For j =1,2,…, k −2, letWe prove thatandwhere and are the largest eigenvalue of the Laplacian matrix and adjacency matrix of T, respectively. These bounds give better results than those obtained in [D. Stevanović, Linear Algebra Appl. 360 (2003) 35–42] except if δ 1 = Δ. [Copyright &y& Elsevier]

Abstract: Let be an unweighted rooted tree of k levels such that in each level the vertices have equal degree. Let d k−j+1 denotes the degree of the vertices in the level j. We find the eigenvalues of the adjacency matrix and of the Laplacian matrix of . They are the eigenvalues of principal submatrices of two nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for both matrices are , and , while the diagonal entries are zeros, in the case of the adjacency matrix, and d j , 1⩽ j ⩽k, in the case of the Laplacian matrix. Moreover, we give some results concerning to the multiplicity of the above mentioned eigenvalues. [Copyright &y& Elsevier]

Something between an expository note and an extended research problem, this article is an invitation to expand the existing literature on a family of graph invariants rooted in linear and multilinear algebra. There are a variety of ways to assign a real n×n matrix K(G) to each n-vertex graph G, so that G and H are isomorphic if and only if K(G) and K(H) are permutation similar. It follows that G and H are isomorphic only if K(G) and K(H) are similar, i.e., that similarity invariants of K(G) are graph theoretic invariants of G, an observation that helps to explain the enormous literature on spectral graph theory. The focus of this article is the permutation part, i.e., on matrix functions that are preserved under permutation similarity if not under all similarity. [Copyright &y& Elsevier]

Let G be a simple undirected graph. For v∈V(G), the 2-degree of v is the sum of the degrees of the vertices adjacent to v. Denote by ρ(G) and μ(G) the spectral radius of the adjacency matrix and the Laplacian matrix of G, respectively. In this paper, we present two lower bounds of ρ(G) and μ(G) in terms of the degrees and the 2-degrees of vertices. [Copyright &y& Elsevier]

Let λ1(G) denote the largest eigenvalue of the adjacency matrix and let μ1(G) denote the largest eigenvalue of the Laplacian matrix of a graph G. It is well known that if a graph G has the largest vertex degree Δ≠0 then√ of Δ&les;λ1(G)&les;ΔandΔ+1&les;μ1(G)&les;2Δ.Thus the gap between the maximum and minimum value of λ1(G) and μ1(G) in the class of graphs with fixed Δ is Θ(Δ). In this note we show that in the class of trees with fixed Δ this gap is just Θ(Δ). Namely, we show that if a tree T has the largest vertex degree Δ thenλ1(T)<2Δ−1andμ1(T)<Δ+2Δ−1&les;λ1(G)&les;Δ and Δ+1&les;μ1(G)&les;2Δ.Thus the gap between the maximum and minimum value of λ1(G) and μ1(G) in the class of graphs with fixed Δ is Θ(Δ). In this note we show that in the class of trees with fixed Δ this gap is just Θ(√ of Δ). Namely, we show that if a tree T has the largest vertex degree Δ thenλ1(T)<2Δ−1andμ1(T)<Δ+2Δ−1). Namely, we show that if a tree T has the largest vertex degree Δ thenλ1(T)<2√ of Δ−1andμ1(T)<Δ+2Δ−1 and μ1(T)<Δ+2√ of Δ−1.New bounds are an improvement for Δ&ges;3. [Copyright &y& Elsevier]

Let G be a graph on n vertices. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. V. Nikiforov studied hybrids of A (G) and D (G) and defined the A α -matrix for every real α ∈ [ 0 , 1 ] as: A α (G) = α D (G) + (1 − α) A (G). In this paper, using a different demonstration technique, we present a way to compare the Estrada index of the A α -matrix with the Estrada index of the adjacency matrix of the graph G. Furthermore, lower bounds for the Estrada index are established. [ABSTRACT FROM AUTHOR]

Abstract: This note deals with the relationship between the total number of -walks in a graph, and the sum of the -th powers of its vertex degrees. In particular, it is shown that the the number of all -walks is upper bounded by the sum of the -th powers of the degrees. [Copyright &y& Elsevier]