共查询到20条相似文献,搜索用时 78 毫秒
1.
设G为具有k个悬挂点的n阶单圈图,刘慧清等给出了这类图的最大谱半径的极图,本文得到了当k≥3时具有第二大谱半径的极图. 相似文献
2.
3.
4.
《中国科学:数学》2016,(8)
设G是一个n阶的简单连通图,符号(d_1,d_2,...,d_n)表示G的度序列,其中d_1≥d_2≥···≥d_n,用符号?(G)表示G的最大度,而符号λ(G)表示G的Laplace谱半径.一个c-圈图是一个恰有n+c-1条边的n阶简单连通图,而符号C(n,?;c)表示最大度等于?的所有n阶c-圈图的集合.本文确定了当0≤c≤1/2(?-1)(?-2)时,C(n,?;c)中所有取得最小Laplace谱半径的极图,并分别确定了当?≥[n+2/3]且d_4≥2或?≥[n/3]+1且d_4=1时,C(n,?;1)中唯一取得最大Laplace谱半径的极图.进一步地,还证明了对于两个n阶的单圈图G和G′,如果?(G)≥[11n/30]+2且?(G)?(G′),则λ(G)λ(G′),并且界"[11n/30]+2"是最佳的. 相似文献
5.
图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1). 相似文献
6.
7.
m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图. 相似文献
8.
k圈图是边数等于顶点数加k-1的简单连通图.文中确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到该上界的极图.此外,文中确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图.最后说明文中所得结论对不含三圈的k圈图的拉普拉斯谱半径也成立. 相似文献
9.
设R(n,d)表示由全体恰含d个环点的n(n≥3)阶本原无向图所构成的集合,F(n,d,k)为R(n,d)中图的第k重上广义本原指数的量大值,1≤d≤n,2≤k≤n-1。本文给出了第k重上广义本原指数达到F(n,d,k)的极图的完全刻画。 相似文献
10.
11.
Didar A. Ali John Baptist Gauci Irene Sciriha Khidir R. Sharaf 《Czechoslovak Mathematical Journal》2016,66(3):971-985
The nullity of a graph G is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex of unique type in the coalescence. Moreover, the nullity of subgraphs obtained by perturbations of the coalescence G is determined relative to the nullity of G. This has direct applications in spectral graph theory as well as in the construction of certain ipso-connected nano-molecular insulators. 相似文献
12.
Forv>d≧3, letm(v, d) be the smallest numberm, such that every convexd-polytope withv vertices has a facet with at mostm vertices. In this paper, bounds form(v, d) are found; in particular, for fixedd≧3, $$\frac{{r - 1}}{r} \leqslant \mathop {\lim \inf }\limits_{\upsilon \to \infty } \frac{{m(\upsilon ,d)}}{\upsilon } \leqslant \mathop {\lim \sup }\limits_{\upsilon \to \infty } \frac{{m(\upsilon ,d)}}{\upsilon } \leqslant \frac{{d - 3}}{{d - 2}}$$ , wherer=[1/3(d+1)]. 相似文献
13.
Jens Vygen 《Discrete Mathematics》2011,(1):1
We present tight bounds on splitting trees into “small” subtrees. 相似文献
14.
J. Cutler 《Discrete Mathematics》2009,309(9):2749-2754
We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac’s theorem on the existence of Hamiltonian cycles. Namely, we prove for 1≤k≤n−2 if G is a connected graph with A⊂V(G) such that dG(v)≥k for all v∈A, then there exists a subtree T of G such that V(T)⊃A and for all v∈A. 相似文献
15.
The Laplacian spectral radii of unicyclic and bicyclic graphs with n vertices and k pendant vertices
JiMing Guo 《中国科学 数学(英文版)》2010,53(8):2135-2142
In this paper, we determine graphs with the largest Laplacian spectral radius among the unicyclic and the bicyclic graphs on n vertices with k pendant vertices, respectively. 相似文献
16.
17.
18.
Mekkia Kouider 《Journal of Graph Theory》1994,18(8):757-776
“If G is a 2-connected graph with n vertices and minimum degree d, then the vertices of G can be covered by less than n/d cycles. This settles a conjecture of Enomoto, Kaneko and Tuza for 2-connected graphs.” 相似文献
19.
20.
Recently, various authors have obtained results about the existence of long cycles in graphs with a given minimum degreed. We extend these results to the case where only some of the vertices are known to have degree at leastd, and we want to find a cycle through as many of these vertices as possible. IfG is a graph onn vertices andW is a set ofw vertices of degree at leastd, we prove that there is a cycle through at least
vertices ofW. We also find the extremal graphs for this property.Research supported in part by NSF Grant DMS 8806097 相似文献