共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
An approach, based on the Smith Normal Form, is introduced to study the spectra of symmetric matrices with a given graph.
The approach serves well to explain how the path cover number (resp. diameter of a tree T) is related to the maximal multiplicity MaxMult(T) occurring for an eigenvalue of a symmetric matrix whose graph is T (resp. the minimal number q(T) of distinct eigenvalues over the symmetric matrices whose graphs are T). The approach is also applied to a more general class of connected graphs G, not necessarily trees, in order to establish a lower bound on q(G). 相似文献
3.
In Wang and Xu (2006) [15] and [16] the authors introduced a family of graphs Hn and gave some methods for finding graphs among this family that are determined by their generalized spectra. This paper is a continuation of our previous work. We further show that almost all graphs in Hn are determined by their generalized spectra. This gives some evidences for the conjecture that almost all graphs are determined by their generalized spectra. 相似文献
4.
《Discrete Mathematics》2019,342(10):2770-2782
“Which graphs are determined by their spectrum (DS for short)?” is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized -spectrum. A graph is said to be determined by the generalized -spectrum (DGQS for short) if, for any graph , and have the same -spectrum and so do their complements imply that is isomorphic to . We give a simple arithmetic condition for a graph being DGQS. More precisely, let be a graph with adjacency matrix and degree diagonal matrix . Let be the signless Laplacian matrix of , and ( is the all-ones vector) be the -walk matrix. We show that if (which is always an integer) is odd and square-free, then is DGQS. 相似文献
5.
A note on the spectral characterization of dumbbell graphs 总被引:1,自引:0,他引:1
Jianfeng Wang Qiongxiang Huang Francesco Belardo Enzo M. Li Marzi 《Linear algebra and its applications》2009,431(10):1707-1714
The dumbbell graph, denoted by Da,b,c, is a bicyclic graph consisting of two vertex-disjoint cycles Ca and Cb joined by a path Pc+3 (c-1) having only its end-vertices in common with the two cycles. By using a new cospectral invariant for (r,r+1)-almost regular graphs, we will show that almost all dumbbell graphs (without cycle C4 as a subgraph) are determined by the adjacency spectrum. 相似文献
6.
7.
Haicheng Ma 《Discrete Mathematics》2010,310(24):3648-3652
A graph is said to be determined by its adjacency spectrum (DS for short) if there is no other non-isomorphic graph with the same spectrum. In this paper, we focus our attention on the spectral characterization of the union of complete multipartite graph and some isolated vertices, and all its cospectral graphs are obtained. By the results, some complete multipartite graphs determined by their adjacency spectrum are also given. This extends several previous results of spectral characterization related to the complete multipartite graphs. 相似文献
8.
9.
Edwin R. van Dam 《Discrete Mathematics》2009,309(3):576-2638
In [E.R. van Dam, W.H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003), 241-272] we gave a survey of answers to the question of which graphs are determined by the spectrum of some matrix associated to the graph. In particular, the usual adjacency matrix and the Laplacian matrix were addressed. Furthermore, we formulated some research questions on the topic. In the meantime, some of these questions have been (partially) answered. In the present paper we give a survey of these and other developments. 相似文献
10.
Aleksandar Ili? Milan Baši? 《Applied mathematics and computation》2011,218(7):3470-3482
Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICGn(D) has the vertex set Zn = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even. 相似文献
11.
Luhua Wang 《Linear and Multilinear Algebra》2013,61(12):2396-2405
A clover graph is obtained from a 3-rose graph by attaching a path to the vertex of degree six, where a 3-rose graph consists of three cycles with precisely one common vertex. In this paper, it is proved that all clover graphs are determined by their Laplacian spectra. 相似文献
12.
We show that the Smith normal form of every skew-Hadamard matrix of order 4m is diag[1,2,...,2, 2m,...,2m,4m] 相似文献
13.
《Discrete Mathematics》2022,345(8):112918
Characterizing graphs by the spectra of various matrices associated with the graphs has long been an important topic in spectral graph theory. However, it is generally very hard to show a given graph to be determined by its spectrum. This paper gives a simple criterion for a tournament to be determined by its adjacency spectrum. More precisely, let G be a tournament of order n with adjacency matrix A, and be its walk matrix, where e is the all-one vector. We show that, for any self-converse tournament G, if is square-free, then G is uniquely determined by its adjacency spectrum among all tournaments. The result is somewhat unexpected, which was achieved by employing some recent tools developed by the second author for showing a graph to be determined by its generalized spectrum. The key observation is that for a tournament G, the complement of G coincides with the converse of G, and hence a certain equivalence between the ordinary adjacency spectrum and the generalized (skew)-adjacency spectrum for G can be established. Moreover, some equivalent formulations of the above result, as well as some related ones are also presented. 相似文献
14.
E.R. van Dam W.H. Haemers E. Spence 《Journal of Combinatorial Theory, Series A》2006,113(8):1805-1820
We characterize the distance-regular Ivanov-Ivanov-Faradjev graph from the spectrum, and construct cospectral graphs of the Johnson graphs, Doubled Odd graphs, Grassmann graphs, Doubled Grassmann graphs, antipodal covers of complete bipartite graphs, and many of the Taylor graphs. We survey the known results on cospectral graphs of the Hamming graphs, and of all distance-regular graphs on at most 70 vertices. 相似文献
15.
16.
We conjecture a strong property for the up and down maps U and D in an r-differential poset: DU + tI and UD + tI have Smith normal forms over . In particular, this would determine the integral structure of the maps U, D, UD, DU, including their ranks in any characteristic. As evidence, we prove the conjecture for the Young-Fibonacci lattice Y
F studied by Okada and its r-differential generalizations Z(r), as well as verifying many of its consequences for Young’s lattice Y and the r-differential Cartesian products Y
r
. 相似文献
17.
Nair Abreu Domingos M. Cardoso Paula Carvalho Cybele T.M. Vinagre 《Discrete Mathematics》2017,340(1):3235-3244
Consider two graphs and . Let be the lexicographic product of and , where is the lexicographic product of the graph by itself times. In this paper, we determine the spectrum of and when and are regular and the Laplacian spectrum of and for and arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10100 ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers. 相似文献
18.
A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let Ne(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈Ne(u) and y∈Ne(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22]. 相似文献
19.
We show that any connected regular graph with d+1 distinct eigenvalues and odd-girth 2d+1 is distance-regular, and in particular that it is a generalized odd graph. 相似文献
20.
Xiaoling Ma 《Linear and Multilinear Algebra》2016,64(12):2474-2485
A rose graph with p petals (or p-rose graph) is a graph obtained by taking p cycles with just a vertex in common. In this paper, we prove that all 4-rose graphs are determined by their signless Laplacian spectra. 相似文献