48 results on '"Adjacency matrix"'
Search Results
2. A Unified Framework for Optimization-Based Graph Coarsening.
- Author
-
Kumar, Manoj, Sharma, Anurag, and Kumar, Sandeep
- Subjects
- *
MACHINE learning , *LAPLACIAN matrices , *MATHEMATICAL regularization - Abstract
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]
- Published
- 2023
3. Graph Theory: A Lost Component for Development in Nigeria.
- Author
-
Babarinsa, Olayiwola
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICS , *RESEARCH - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
4. On hyper-Hamiltonicity in graphs.
- Author
-
Del-Vecchio, Renata R., Vinagre, Cybele T.M., and Pereira, Guilherme B.
- Subjects
- *
HAMILTONIAN graph theory , *LAPLACIAN matrices , *EIGENVALUES - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
5. A Unified Framework for Structured Graph Learning via Spectral Constraints.
- Author
-
Kumar, Sandeep, Jiaxi Ying, de M. Cardoso, Jose Vinícius, and Palomar, Daniel P.
- Subjects
- *
COMBINATORIAL optimization , *GRAPH theory , *REGULAR graphs , *SPECTRAL theory , *LAPLACIAN matrices , *NP-hard problems , *CONSTRAINT programming - Abstract
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]
- Published
- 2020
6. A characterization of oriented hypergraphic Laplacian and adjacency matrix coefficients.
- Author
-
Chen, Gina, Liu, Vivian, Robinson, Ellen, Rusnak, Lucas J., and Wang, Kyle
- Subjects
- *
HYPERGRAPHS , *LAPLACIAN matrices , *COEFFICIENTS (Statistics) , *MATHEMATICAL bounds , *GENERALIZATION - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
7. On the multiplicity of α as an eigenvalue of Aα(G) of graphs with pendant vertices.
- Author
-
Cardoso, Domingos M., Pastén, Germain, and Rojo, Oscar
- Subjects
- *
EIGENVALUES , *MULTIPLICITY (Mathematics) , *GEOMETRIC vertices , *SET theory , *EIGENANALYSIS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
8. On the determinant of the Laplacian matrix of a complex unit gain graph.
- Author
-
Wang, Yi, Gong, Shi-Cai, and Fan, Yi-Zheng
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL complexes , *UNDIRECTED graphs , *PATHS & cycles in graph theory - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
9. LEXICOGRAPHIC POLYNOMIALS OF GRAPHS AND THEIR SPECTRA.
- Author
-
Cardoso, Domingos M., Carvalho, Paula, Rama, Paula, Simić, Slobodan K., and Stanić, Zoran
- Subjects
- *
LEXICOGRAPHY , *GRAPHIC methods , *INTEGERS , *LAPLACIAN operator , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
10. Spectral characterizations of signed lollipop graphs.
- Author
-
Belardo, Francesco and Petecki, Paweł
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL analysis , *BOUNDARY value problems , *NUMERICAL analysis - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
11. The largest Laplacian and adjacency indices of complete caterpillars of fixed diameter.
- Author
-
Abreu, Nair, Rojo, Oscar, and Lenes, Eber
- Subjects
- *
LAPLACIAN matrices , *CATERPILLARS , *GEOMETRIC vertices , *MATHEMATICS , *INTEGERS - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
12. Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues.
- Author
-
Charles, Zachary B., Farber, Miriam, Johnson, Charles R., and Kennedy-Shaffer, Lee
- Subjects
- *
EIGENVALUES , *MATRICES (Mathematics) , *MATHEMATICAL bounds , *LAPLACIAN matrices , *UNDIRECTED graphs , *GRAPH theory - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
13. The minimum rank of universal adjacency matrices
- Author
-
Ahmadi, B., Alinaghipour, F., Fallat, Shaun M., Fan, Yi-Zheng, Meagher, K., and Nasserasr, S.
- Subjects
- *
MATRICES (Mathematics) , *GRAPH theory , *PATHS & cycles in graph theory , *MONOTONIC functions , *MULTIPLICITY (Mathematics) , *COMBINATORICS - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
14. Eigenvalues of certain weighted graphs joined at their roots having cliques at some levels
- Author
-
Medina, Luis and Rojo, Oscar
- Subjects
- *
EIGENVALUES , *GRAPH theory , *ROOTS of equations , *PATHS & cycles in graph theory , *MULTIPLICITY (Mathematics) , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
15. An upper bound on the largest signless Laplacian of an odd unicyclic graph.
- Author
-
COLLAO, MACARENA, PIZARRO, PAMELA, and ROJO, OSCAR
- Subjects
- *
MATHEMATICAL bounds , *LAPLACIAN matrices , *GRAPH theory , *EIGENVALUES , *TREE graphs , *UNIQUENESS (Mathematics) , *GENERALIZATION - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
16. Line graph of combinations of generalized Bethe trees: Eigenvalues and energy
- Author
-
Rojo, Oscar and Jiménez, Raúl D.
- Subjects
- *
GRAPH theory , *TREE graphs , *EIGENVALUES , *FORCE & energy , *PATHS & cycles in graph theory , *MATHEMATICAL analysis , *COMBINATORICS - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
17. Universal adjacency matrices with two eigenvalues
- Author
-
Haemers, W.H. and Omidi, G.R.
- Subjects
- *
EIGENVALUES , *PATHS & cycles in graph theory , *GRAPH theory , *MATRICES (Mathematics) , *COMPLETE graphs , *COMBINATORICS - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
18. On Hadamard diagonalizable graphs
- Author
-
Barik, S., Fallat, S., and Kirkland, S.
- Subjects
- *
GRAPH theory , *HADAMARD matrices , *LINE geometry , *HARMONIC functions , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
19. Line graph eigenvalues and line energy of caterpillars
- Author
-
Rojo, Oscar
- Subjects
- *
GRAPH theory , *EIGENVALUES , *MATRICES (Mathematics) , *HARMONIC functions , *MATHEMATICAL sequences , *MATHEMATICAL formulas , *THEORY of distributions (Functional analysis) , *TREE graphs - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
20. Enumeration of spanning trees of graphs with rotational symmetry
- Author
-
Yan, Weigen and Zhang, Fuji
- Subjects
- *
SPANNING trees , *MATHEMATICAL symmetry , *LAPLACIAN operator , *MATRICES (Mathematics) , *TREE graphs , *NUMERICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
21. Conjectures on index and algebraic connectivity of graphs
- Author
-
Das, Kinkar Ch.
- Subjects
- *
GRAPH connectivity , *ALGEBRA , *SET theory , *MATCHING theory , *NUMBER theory , *SPECTRAL theory - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
22. Energy of line graphs
- Author
-
Gutman, Ivan, Robbiano, María, Martins, Enide Andrade, Cardoso, Domingos M., Medina, Luis, and Rojo, Oscar
- Subjects
- *
GRAPH theory , *LINE geometry , *MATRICES (Mathematics) , *ADDITION (Mathematics) , *EIGENVALUES , *INCIDENCE functions , *LAPLACIAN operator - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
23. Spectral characterization of some weighted rooted graphs with cliques
- Author
-
Rojo, Oscar and Medina, Luis
- Subjects
- *
GRAPH theory , *SPECTRAL theory , *TREE graphs , *GENERALIZABILITY theory , *TOPOLOGICAL degree , *GRAPH connectivity , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
24. Applications of recurrence relations for the characteristic polynomials of Bethe trees
- Author
-
Robbiano, María and Trevisan, Vilmar
- Subjects
- *
POINT mappings (Mathematics) , *POLYNOMIALS , *TREE graphs , *TOPOLOGICAL degree , *INVARIANTS (Mathematics) , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
25. Improved bounds for the Laplacian energy of Bethe trees
- Author
-
Robbiano, Marı´a and Jiménez, Raúl
- Subjects
- *
TREE graphs , *LAPLACIAN operator , *BIPARTITE graphs , *MATRICES (Mathematics) , *GRAPH theory , *SPECTRAL theory - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
26. On the characteristic and Laplacian polynomials of trees
- Author
-
Heydari, Abbas and Bijan Taeri
- Subjects
- *
LAPLACIAN operator , *POLYNOMIALS , *ARBITRARY constants , *LINEAR algebra , *TOPOLOGICAL degree , *GENERALIZABILITY theory , *MATRICES (Mathematics) , *VERTEX operator algebras - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
27. Spectral characterizations of sun graphs and broken sun graphs.
- Author
-
Boulet, Romain
- Subjects
- *
GRAPHIC methods , *CHARTS, diagrams, etc. , *GRAPH theory , *LAPLACIAN operator , *MATHEMATICS - Abstract
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]
- Published
- 2009
28. Spectra of copies of a generalized Bethe tree attached to any graph
- Author
-
Rojo, Oscar
- Subjects
- *
SPECTRAL theory , *TREE graphs , *VERTEX operator algebras , *EIGENVALUES , *LAPLACIAN operator , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
29. Spectra of generalized Bethe trees attached to a path
- Author
-
Rojo, Oscar and Medina, Luis
- Subjects
- *
VERTEX operator algebras , *EIGENVALUES , *MATRICES (Mathematics) , *ALGEBRA - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
30. SPECTRAL PROPERTY OF CERTAIN CLASS OF GRAPHS ASSOCIATED WITH GENERALIZED BETHE TREES AND TRANSITIVE GRAPHS.
- Author
-
Yi-Zheng Fan, Shuang-Dong Li, and Dong Liang
- Subjects
- *
EIGENVALUES , *MATRICES (Mathematics) , *LAPLACIAN operator , *PARTIAL differential equations , *MULTIPLY transitive groups , *FINITE groups , *COMPUTATIONAL mathematics - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
31. Spectra of weighted generalized Bethe trees joined at the root
- Author
-
Rojo, Oscar
- Subjects
- *
MATRICES (Mathematics) , *SPECTRUM analysis , *EIGENVALUES , *UNIVERSAL algebra - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
32. On the spectra of some graphs like weighted rooted trees
- Author
-
Fernandes, Rosário, Gomes, Helena, and Martins, Enide Andrade
- Subjects
- *
MATRICES (Mathematics) , *EIGENVALUES , *SPECTRUM analysis , *UNIVERSAL algebra - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
33. The Laplacian spectral radius of graphs on surfaces
- Author
-
Lin, Liang
- Subjects
- *
MATRICES (Mathematics) , *ABSTRACT algebra , *UNIVERSAL algebra , *LINEAR algebra - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
34. New upper bounds on the spectral radius of unicyclic graphs
- Author
-
Rojo, Oscar
- Subjects
- *
MATRICES (Mathematics) , *GRAPH theory , *UNIVERSAL algebra , *LINEAR algebra - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
35. An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree
- Author
-
Rojo, Oscar and Robbiano, María
- Subjects
- *
MATRICES (Mathematics) , *EIGENVALUES , *RADIAL bone , *ALGEBRA - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
36. The largest eigenvalue of unicyclic graphs
- Author
-
Hu, Shengbiao
- Subjects
- *
MATRICES (Mathematics) , *MATHEMATICS , *MATHEMATICAL analysis , *GRAPH theory - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
37. The spectra of a graph obtained from copies of a generalized Bethe tree
- Author
-
Rojo, Oscar
- Subjects
- *
TREE graphs , *EIGENVALUES , *MATRICES (Mathematics) , *GRAPHIC methods , *HARMONIC functions - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
38. On the spectra of some weighted rooted trees and applications
- Author
-
Rojo, Oscar and Robbiano, María
- Subjects
- *
TREE graphs , *EIGENVALUES , *MATRICES (Mathematics) , *LAPLACE transformation , *DEGREES of freedom , *TOPOLOGICAL degree - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
39. Characterization of graphs having extremal Randić indices
- Author
-
Das, Kinkar Ch. and Kwak, Jin Ho
- Subjects
- *
MATHEMATICS , *LINEAR algebra , *ALGEBRA , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
40. The spectra of some trees and bounds for the largest eigenvalue of any tree
- Author
-
Rojo, Oscar
- Subjects
- *
TREE graphs , *EIGENVALUES , *MATRICES (Mathematics) , *LAPLACIAN operator - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
41. On the spectra of certain rooted trees
- Author
-
Rojo, Oscar
- Subjects
- *
TREE graphs , *EIGENVALUES , *MATRICES (Mathematics) , *UNIVERSAL algebra - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
42. Improved bounds for the largest eigenvalue of trees
- Author
-
Rojo, Oscar
- Subjects
- *
VERTEX detectors , *OPERATOR algebras , *LINEAR algebra , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
43. The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
- Author
-
Rojo, Oscar and Soto, Ricardo
- Subjects
- *
MATRICES (Mathematics) , *EIGENVALUES , *SPECTRUM analysis , *UNIVERSAL algebra - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
44. Immanantal invariants of graphs
- Author
-
Merris, Russell
- Subjects
- *
MATRICES (Mathematics) , *GRAPH theory , *INVARIANTS (Mathematics) , *ALGEBRA - Abstract
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 matrixK(G) to eachn -vertex graphG , so thatG andH are isomorphic if and only ifK(G) andK(H) are permutation similar. It follows thatG andH are isomorphic only ifK(G) andK(H) are similar, i.e., that similarity invariants ofK(G) are graph theoretic invariants ofG , 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]- Published
- 2005
- Full Text
- View/download PDF
45. On the spectral radius of graphs
- Author
-
Yu, Aimei, Lu, Mei, and Tian, Feng
- Subjects
- *
GRAPHIC methods , *LAPLACIAN operator , *PARTIAL differential equations , *GEOMETRICAL drawing - Abstract
Let
G be a simple undirected graph. Forv∈V(G) , the 2-degree ofv is the sum of the degrees of the vertices adjacent tov . Denote byρ(G) andμ(G) the spectral radius of the adjacency matrix and the Laplacian matrix ofG , 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]- Published
- 2004
- Full Text
- View/download PDF
46. Bounding the largest eigenvalue of trees in terms of the largest vertex degree
- Author
-
Stevanović, Dragan
- Subjects
- *
EIGENVALUES , *MATRICES (Mathematics) - Abstract
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Δ ⩽λ1(G)⩽Δand Δ+1⩽μ1(G)⩽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 Δ−1 and μ1(T)<Δ+2 ). Namely, we show that if a treeΔ−1 ⩽λ1(G)⩽Δ and Δ+1⩽μ1(G)⩽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 Δ T has the largest vertex degreeΔ thenλ1(T)<2 Δ−1 and μ1(T)<Δ+2 Δ−1 ). Namely, we show that if a tree T has the largest vertex degreeΔ thenλ1(T)<2√ ofΔ−1 and μ1(T)<Δ+2 Δ−1 and μ1(T)<Δ+2√ ofΔ−1 .New bounds are an improvement forΔ⩾3 . [Copyright &y& Elsevier]- Published
- 2003
47. A Note on the Estrada Index of the A α -Matrix.
- Author
-
Rodríguez, Jonnathan, Nina, Hans, and Sztrik, János
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
48. Number of walks and degree powers in a graph
- Author
-
Fiol, M.A. and Garriga, E.
- Subjects
- *
GRAPH theory , *PATHS & cycles in graph theory , *TOPOLOGICAL degree , *BETWEENNESS relations (Mathematics) , *SET theory , *MATRICES (Mathematics) , *ADDITION (Mathematics) - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.