共查询到20条相似文献,搜索用时 15 毫秒
1.
A multi-fan graph is a graph of the form (Pn1+Pn2+?+Pnk)×b, where b is a universal vertex, and Pn1+Pn2+?+Pnk is the disjoint union of paths Pni(ni?1) for i=1,2,…,k. In particular, if k=1, the multi-fan graph Pn1×b is the classical fan graph Fn1+1. It is proved that all the multi-fan graphs are determined by their Laplacian spectra. 相似文献
2.
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. 相似文献
3.
设G=(V(G),E(G))是一个简单连通图,V(G),E(G)分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构,则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q(n;n_1,n_2,···,nt)和B(n;n_1,n_2),证明了双圈图Q(n;n_1),Q(n;n_1,n_2),Q(n;n_1,n_2,n_3)和双圈图B(n;n_1,n_2)分别由它们的Laplacian谱确定. 相似文献
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.
6.
7.
设图G是简单连通图.如果任何一个与图G关于拉普拉斯矩阵同谱的图,都与图G同构,称图G可由其拉普拉斯谱确定.定义了树Y_n和树F(2,n,1)两类特殊结构的树.利用同谱图线图的特点,证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定. 相似文献
8.
9.
Muhuo Liu 《Czechoslovak Mathematical Journal》2012,62(4):1117-1134
Let W n = K 1 ? C n?1 be the wheel graph on n vertices, and let S(n, c, k) be the graph on n vertices obtained by attaching n-2c-2k-1 pendant edges together with k hanging paths of length two at vertex υ 0, where υ 0 is the unique common vertex of c triangles. In this paper we show that S(n, c, k) (c ? 1, k ? 1) and W n are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that S(n, c, k) and its complement graph are determined by their Laplacian spectra, respectively, for c ? 0 and k ? 1. 相似文献
10.
11.
图和线图的谱性质 总被引:5,自引:0,他引:5
陈晏 《高校应用数学学报(英文版)》2002,17(3):371-376
Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite. 相似文献
12.
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. 相似文献
13.
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. 相似文献
14.
Yasuo Teranishi 《Discrete Mathematics》2002,257(1):183-189
15.
16.
《Discrete Mathematics》2022,345(8):112916
In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using the notion of partitioned tensor products. This extends the construction of Ji, Gong, and Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction [4], and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al. 相似文献
17.
Liang Lin 《Linear algebra and its applications》2008,428(4):973-977
Let G be an n-vertex (n?3) 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)
-
18.
Wang Yi Fan Yizheng Tan Yingying 《高校应用数学学报(英文版)》2007,22(4):478-484
In this paper,an equivalent condition of a graph G with t(2≤t≤n)distinct Laplacian eigenvalues is established.By applying this condition to t=3,if G is regular(neces- sarily be strongly regular),an equivalent condition of G being Laplacian integral is given.Also for the case of t=3,if G is non-regular,it is found that G has diameter 2 and girth at most 5 if G is not a tree.Graph G is characterized in the case of its being triangle-free,bipartite and pentagon-free.In both cases,G is Laplacian integral. 相似文献
19.