共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Yasuo Teranishi 《Linear and Multilinear Algebra》2006,54(3):211-217
We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs. 相似文献
3.
Yasuo Teranishi 《Linear and Multilinear Algebra》2013,61(3):211-217
We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs. 相似文献
4.
C. M. Da Fonseca 《Annali di Matematica Pura ed Applicata》2008,187(2):251-261
A different approach is given to recent results due mainly to R. C. Johnson and A. Leal Duarte on the multiplicities of eigenvalues
of a Hermitian matrix whose graph is a tree. The techniques developed are based on some results of matching polynomials and
used a work by O. L. Heilmann and E. H. Lieb on an apparently unrelated topic.
相似文献
5.
Dongmei Zhu 《Linear algebra and its applications》2010,432(11):2764-2772
In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):
6.
We introduce a new graph-theoretic invariant ω(G) for a simple graph G, and relate it to the third smallest Laplace eigenvalue of G. 相似文献
7.
We introduce a new graph-theoretic invariant ω(G) for a simple graph G, and relate it to the third smallest Laplace eigenvalue of G. 相似文献
8.
9.
ZhangXiaodong LiJiongsheng WangPing 《高校应用数学学报(英文版)》1999,14(2):197-202
The Merris‘ conjectures for threshold graphs and d-regular graphs are proved. Andthe one of the conjectures of Merris holds for trees is also proved. 相似文献
10.
Hye Kyung Kim 《Discrete Mathematics》2008,308(4):555-564
For an abelian group Γ, a formula to compute the characteristic polynomial of a Γ-graph has been obtained by Lee and Kim [Characteristic polynomials of graphs having a semi-free action, Linear algebra Appl. 307 (2005) 35-46]. As a continuation of this work, we give a computational formula for generalized characteristic polynomial of a Γ-graph when Γ is a finite group. Moreover, after showing that the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, we compute the reciprocals of the Bartholdi zeta functions of wheels and complete bipartite graphs as an application of our formula. 相似文献
11.
T. Fernández 《Monatshefte für Mathematik》2005,145(2):95-96
We give an easy proof of a result in [1] generalizing the well-known Borsuks non-retraction theorem. 相似文献
12.
Let A and B be n?×?n matrices over an algebraically closed field F. The pair ( A,?B ) is said to be spectrally complete if, for every sequence c1,…,cn ∈F such that det (AB)=c1 ,…,cn , there exist matrices A′,B,′∈F,n×n similar to A,?B, respectively, such that A′B′ has eigenvalues c1,…,cn . In this article, we describe the spectrally complete pairs. Assuming that A and B are nonsingular, the possible eigenvalues of A′B′ when A′ and B′ run over the sets of the matrices similar to A and B, respectively, were described in a previous article. 相似文献
13.
Bao-Xuan Zhu 《Linear algebra and its applications》2011,434(9):2030-2041
In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices. 相似文献
14.
We find lower bounds on the difference between the spectral radius λ1 and the average degree of an irregular graph G of order n and size e. In particular, we show that, if n ? 4, then
15.
For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges. 相似文献
16.
Let G be a graph with n vertices and m edges. Let λ1, λ2, … , λn be the eigenvalues of the adjacency matrix of G, and let μ1, μ2, … , μn be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences. 相似文献
17.
For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree. 相似文献
18.
Servet Martí nez Jaime San Martí n Xiao-Dong Zhang 《Linear and Multilinear Algebra》2004,52(5):335-347
In this article, we characterize generalized ultrametric matrices whose inverses are tree-diagonal. This generalizes the results of McDonald, Nabben, Neumann, Schneider and Tsatsomeros for tri-diagonal matrices. 相似文献
19.
20.
Yi Wang 《Linear algebra and its applications》2010,433(1):19-2155
In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound. 相似文献