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]

In this paper, we provide a characterization of fractional revival between twin vertices in a weighted graph with respect to its adjacency, Laplacian and signless Laplacian matrices. As an application, we characterize fractional revival between apexes of double cones. [ABSTRACT FROM AUTHOR]

We formalize the notion of a sedentary vertex and present a relaxation of the concept of a sedentary family of graphs introduced by Godsil (Linear Algebra Appl 614:356–375, 2021. https://doi.org/10.1016/j.laa.2020.08.027). We provide sufficient conditions for a given vertex in a graph to exhibit sedentariness. We also show that a vertex with at least two twins (vertices that share the same neighbours) is sedentary. We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary, which reveals that, even though strong cospectrality is a necessary condition for pretty good state transfer, there are strongly cospectral vertices which resist high probability state transfer to other vertices. Moreover, we derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n with domination number γ (G). Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue λ of G with multiplicity m G (λ) , it holds that γ (G) ≤ n − m G (λ). Using techniques from the theory of star sets, in this work we prove that the same bound holds when λ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the p -domination number, and we apply it to extend the aforementioned spectral bound to the p -domination number using the adjacency and Laplacian eigenvalue multiplicities. [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]

In this article, we consider the generalization of the Laplacian matrix for hypergraphs to obtain several results related to spectral properties of hypergraphs. This generalization of Laplacian matrix was defined in 2021 by Anirban Banerjee. We first supply a necessary and sufficient condition on the Laplacian spectral radius of hypergraphs such that the complement of that hypergraph is connected. We give bounds for the Laplacian spectral radius of k -uniform hypergraphs in terms of some invariants of hypergraph, such as the maximum degree, minimum degree, first Zagreb index, and the chromatic number. As an application of these results, some upper bounds of the Nordhaus-Gaddum type are obtained for the sum of Laplacian spectral radius of a k -uniform hypegraphs and its complement, and product of Laplacian spectral radius of a k -uniform hypegraphs and its complement. It is known that the second largest Laplacian eigenvalue for graphs is greater or equal to the second highest degree of graphs. We show by an example that this result is not true for 3-uniform hypergraphs in general. Finally, we supply a class of 3-uniform hypergraphs for which the second largest Laplacian eigenvalue is greater or equal to the second highest degree. [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]

In this paper, we introduce a class of treelike networks generated by motifs with single root node. We study the spectral properties of treelike networks by studying the behaviors of the corresponding adjacency matrix and Laplacian matrix. First, we get the adjacency matrix and Laplacian matrix of this treelike network. Then, we analyze symmetry of eigenvalues, multiplicity of eigenvalue 0 and prove that its largest eigenvalue is strictly monotonically increasing and convergent. Finally, we introduce a new method to prove that the largest eigenvalue of the Laplacian matrix is strictly monotonically increasing and convergent. Also, we obtain that its smallest nonzero eigenvalue is strictly monotonically decreasing and convergent. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider weighted coupled cell networks, that is networks where the interactions between any two cells have an associated weight that is a real valued number. Weighted networks are ubiquitous in real-world applications. We consider a dynamical systems perspective by associating with each network a set of continuous dynamical systems, the ones that respect the graph structure of the network. For weighted networks it is natural for the admissible coupled cell systems to have an additive input structure. We present a characterization of the synchrony subspaces and the antisynchrony subspaces for a weighted network depending on the restrictions that are imposed in their admissible input-additive coupled cell systems. These subspaces are flow invariant by those systems and are generalized polydiagonal subspaces, that is, are characterized by conditions on the cell coordinates of the types xi = xj and/or xk = xl and/or xm = 0. The existence and identification of the synchrony and antisynchrony subspaces for a weighted network are deeply relevant from the applications and dynamics points of view. Our characterization of the synchrony and antisynchrony subspaces of a weighted network follows from our results where we give necessary and sufficient conditions for a generalized polydiagonal to be invariant by the adjacency matrix and/or the Laplacian matrix of the network. [ABSTRACT FROM AUTHOR]

Let G be an arbitrary group. We define a gain-line graph for a gain graph (Γ , ψ) through the choice of an incidence G -phase matrix inducing ψ. We prove that the switching equivalence class of the gain function on the line graph L (Γ) does not change if one chooses a different G -phase inducing ψ or a different representative of the switching equivalence class of ψ. In this way, we generalize to any group some results proven by N. Reff in the abelian case. The investigation of the orbits of some natural actions of G on the set H Γ of G -phases of Γ allows us to characterize gain functions on Γ, gain functions on L (Γ) , their switching equivalence classes and their balance property. The use of group algebra valued matrices plays a fundamental role and, together with the matrix Fourier transform, allows us to represent a gain graph with Hermitian matrices and to perform spectral computations. Our spectral results also provide some necessary conditions for a gain graph to be a gain-line graph. [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]

Let G = (V,E) be a simple, undirected graph with maximum and minimum degree Δ and δ respectively, and let A be the adjacency matrix and Q be the Laplacian matrix of G. In the past decades, the Laplacian spectrum has received much more attention, since it has been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. In this paper, we will compute lower and upper bounds for the largest Laplacian eigenvalue which is related to a given maximum and minimum degree and a given number of vertices and edges. We will also compare our results in this paper with other published results. [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]

In recent years, weighted networks have been extensively studied in various fields. This paper studies characteristic polynomial of adjacency or Laplacian matrix for weighted treelike networks. First, a class of weighted treelike networks with a weight factor is introduced. Then, the relationships of adjacency or the Laplacian matrix at two successive generations are obtained. Finally, according to the operation of the block matrix, we obtain the analytic expression of the characteristic polynomial of the adjacency or the Laplacian matrix. The obtained results lay the foundation for the future study of adjacency spectrum or Laplacian spectrum. [ABSTRACT FROM AUTHOR]

Abstract We investigate signed graph whose Laplacian matrix has just two distinct eigenvalues. All simple connected signed graphs with maximum degree at most 4 and just two distinct Laplacian eigenvalues are characterized in this paper. [ABSTRACT FROM AUTHOR]

Abstract An expression of the coefficient of immanantal polynomial of an n × n matrix is present. Moreover, we give expressions of the coefficient of immanantal polynomials of combinatorial matrices (adjacency matrix, Laplacian matrix, signless Laplacian matrix). As applications, we show that the immanantal polynomials for Laplacian matrix and signless Laplacian matrix of bipartite graphs are the same. This is a generalization of the characteristic polynomial for Laplacian matrix and signless Laplacian matrix of bipartite graphs. Furthermore, we consider the relations between the characteristic polynomial and the immanantal polynomial for trees. [ABSTRACT FROM AUTHOR]

Let G 1 , G 2 and H be three graphs on disjoint sets of vertices and G 1 has m 1 edges. Let S (G 1 , H) be the graph obtained from G 1 and H in the following way: (1) Delete all the edges of G 1 and consider m 1 disjoint copies of H. (2) Join each vertex of the i th copy of H to the end vertices of the i th edge of G 1 . Let G 1 (∨ H) G 2 be the graph obtained from S (G 1 , H) by joining each vertex of G 1 with each vertex of G 2. In this paper, we determine the adjacency (respectively, Laplacian, signless Laplacian) spectrum of G 1 (∨ H) G 2 in terms of those of G 1 , G 2 and H. As an application, we construct infinite pairs of cospectral graphs. [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 be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [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]

A weighted Bethe graphBis obtained from a weighted generalized Bethe tree by identifying each set of children with the vertices of a graph belonging to a familyFof graphs. The operation of identifying the root vertex of each ofrweighted Bethe graphs to the vertices of a connected graphof orderris introduced as the-concatenation of a family ofrweighted Bethe graphs. It is shown that the Laplacian eigenvalues (whenFhas arbitrary graphs) as well as the signless Laplacian and adjacency eigenvalues (when the graphs inFare all regular) of the-concatenation of a family of weighted Bethe graphs can be computed (in a unified way) using the stable and low computational cost methods available for the determination of the eigenvalues of symmetric tridiagonal matrices. Unlike the previous results already obtained on this topic, the more general context of families of distinct weighted Bethe graphs is herein considered. [ABSTRACT FROM PUBLISHER]

Let λ2(G) and τ (G) denote the second largest eigenvalue and themaximum number of edge-disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of τ (G), Cioaba andWong conjectured that for any integers d, k ≥ 2 and a d-regular graph G, if λ2(G) < d - 2k-1/d+1, then τ (G) ≥ k. They proved the conjecture for k = 2, 3, and presented evidence for the cases when k ≥ 4. Thus the conjecture remains open for k ≥ 4. We propose a more general conjecture that for a graph G with minimum degree δ ≥ 2k ≥ 4, if λ2(G) < δ - 2k-1 δ+1, then τ (G) ≥ k. In this article, we prove that for a graph G with minimum degree δ, each of the following holds. (i) For k {2, 3}, if δ ≥ 2k and λ2(G) < δ - 2k-1/δ+1, then τ (G) ≥ k. (ii) For k ≥ 4, if δ ≥ 2k and λ2(G) < δ - 3k-1/δ+1, then τ (G) ≥ k. Our results sharpen theorems of Cioaba and Wong and give a partial solution to Cioaba and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree δ ≥ k ≥ 2, if λ2(G) < δ - 2(k-1) δ+1, then the edge connectivity is at least k, which generalizes a former result of Cioab? a. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on τ (G) and edge connectivity. [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]

Letandbe two vertex disjoint graphs of ordersandrespectively, whereandLetbe a specified edge ofsuch thatis isomorphic toLetbe a subset of the edge set ofand letdenote the subgraph ofinduced byLetbe the graph obtained by taking one copy ofandvertex disjoint copies ofand then pasting the edgein theth copy ofwith the edgewhereThen the copies of the graphthat are pasted to the edgesare called as edge-pockets, and we sayis a graph withedge-pockets. In this article, we prove some results describing the Laplacian (resp. adjacency) spectrum ofusing the Laplacian (resp. adjacency) spectra ofandThe complete Laplacian (resp. adjacency) spectrum ofis also described in some particular cases. As an application, we show that these results enable us to construct infinitely many pairs of Laplacian (resp. adjacency) cospectral graphs. [ABSTRACT FROM AUTHOR]

The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the graphs for which the bounds are attained. Moreover, some known lower bounds on the spectral radius and the Laplacian spectral radius of unweighted graphs can be deduced from the bounds. [ABSTRACT FROM AUTHOR]

In this article, we study problems where one has to prove that certain graph parameter attains its maximum at the star and its minimum at the path among the trees on a fixed number of vertices. We give many applications of the so-called generalized tree shift which seems to be a powerful tool to attack the problems of the above-mentioned kind. We show that the generalized tree shift increases the largest eigenvalue of the adjacency matrix and Laplacian matrix, decreases the coefficients of the characteristic polynomials of these matrices in absolute value. We will prove similar theorems for the independence polynomial and the edge cover polynomial. The generalized tree shift induces a partially ordered set on trees having fixed number of vertices. The smallest element of this poset is the path, largest element is the star. Hence, the above-mentioned results imply the extremality of the path and the star for these parameters. [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]

Let G be a connected graph of order n. The diameter of a graph is the maximum distance between any two vertices of G. In this paper, we will give some bounds on the diameter of G in terms of eigenvalues of adjacency matrix and Laplacian matrix, respectively. [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: 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]