共查询到19条相似文献,搜索用时 250 毫秒
1.
设G是一个简单图,G1∈G,G1在G中的度定义为d(G1)=∑v∈V(G)d(v),其中d(v)为v在G中的度数.主要结果是:设G是n≥3阶几乎无桥的简单连通图,且G≠K(1,n-1)、Q1和Q2,若对G中任何同构于四个顶点路的导出子图I,有d(I)≥2n-6,则G有一个D-闭迹,从而G的线图L(G)是哈密顿图. 相似文献
2.
1引言设G=(V,E)为n阶无向的简单连通图.记N(v)为v的所有相邻点的集合,则d(v)=|N(v)|称为顶点v的度.若d(v)=1,则称v为G的一个悬挂点.设D(G)=diag(d(v1),d(v2),…,d(vn))和A(G)分别表示图G的度对角矩阵和邻接矩阵,则L(G)=D(G)-A(G)称为图G的Laplace矩阵,而Q(G)=D(G)+A(G)称为图G的SignlessLaplace矩阵.用符号Nm×n表示一个m行n列的矩阵,Mn表示一个n阶的方阵.特 相似文献
3.
设G是n阶2-连通图,3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L,若d(u)且如果dL(u,v)=2有(v)=min{,|M3(u)|/2}这里M3(u)={v|dc(u,v)≤3},则G包含长至少为c的圈. 相似文献
4.
5.
设n,m和r是满足r≥2,n≥0,m≥3的整数,且当r是奇数时,假设r≥m-1.称一个图为K1,m-free,如果它不包含以Kt,m为导出的子图.称一个图G为一个(r,n)-临界图,如果在删去G的任意n个点后,剩下G的子图都有一个r-因子,设G是一个Kl,m-free的(n+1)-连通图,且阶为|G|以及r(|G|≥n)是偶数,证明了:如果G的最小度至少是r+n+m-1,阶|G|≥8r5+n,并且对V(G)的任意独立点集{x1,x2}都有|NG(x1)∪NG(x2)|≥(|G|+n)/2,那么G是一个(r,n)-临界图.关于G的最小度和|NG(x1)∪NG(X2)|的下界是紧的。 相似文献
6.
7.
8.
设k,n1和n2是3个正整数,G=(V1,V2;E)是一个二分图,使得|V1|=n1,|V2|=n2,其中n1≥2k+1,n2≥2k+1并且n1-n2≤1.如果对任意不相邻的x∈V1和y∈V2,都有d(x)+d(y)≥2k+2,则G包含k个相互独立的圈.以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题. 相似文献
9.
哈密顿线图的一个充分条件 总被引:7,自引:0,他引:7
对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的. 相似文献
10.
设G为n阶κ正则简单连通图(κ≥2),λ是图G的次根,d(G)是图G的直径,如果G不是二部图,且d(G)≠2,则d(G)≤[log(n-1)/log(κ/λ)],并且当G≌时,这一上界可达. 相似文献
11.
12.
Let G be a3-connected graph with n vertices.The paper proves that if for each pair of verti-ces u and v of G,d(u,v)=2,has|N(u)∩N(v)|≤α(αis the minimum independent set num-ber),and then max{d(u),d(v)|≥n 1/2,then G is a Hamilton connected graph. 相似文献
13.
令Kv表示v个顶点的完全图,G是一个不含孤立点的简单连通图.一个v阶的G-设计是将Kv划分成互不相交的子图,使得每个子图都和G同构,记为G-GD(v).研究六点九边图G11的图设计存在性问题.利用标准的递推构造并结合必要的直接构造,证明除去G11-GD(9)不存在以及G11-GD(18)的存在性未知外,G11-GD(v... 相似文献
14.
设G是一个2-连通赋权图,且G中每一对不相邻顶点u和v都满足d~w(u)+d~w(v)≥2d.Bondy等人证明了G或者包含一个哈密尔顿圈,或者包含一个权至少为2d的圈.如果G不是哈密尔顿图,这个结论意味着G中包含一个权至少为2d的圈.但是当G是哈密尔顿图时,我们不能判断G是否包含一个权至少为2d的圈.这篇文章中,在Fujisawa的一篇文章的启发下,我们证明了当G是triangle-free图并且|V(G)|是奇数时,G中一定包含一个权至少为2d的圈,即使G是哈密尔顿图. 相似文献
15.
16.
任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs" [J East China NormUniv Natur Sci, Sep. 2010, No. 5, 1-13] 中,全面地阐述了近30 年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:
猜想1 设G 为简单连通图, 且G 的每条边含在一个三角形K3 中, 则G 是上可嵌入的.
猜想2 设c 为任意的正数, 则存在一个自然数N(c), 使得对每一个图G, 若G 的点数n ≥ N(c), 且最小度δ(G) ≥ cn, 则G 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题. 相似文献
17.
设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的. 相似文献
18.
利用图的直径和围长来研究图的最大亏格的下界,得到了如下结果:设G是直径为d的简单图,若G的围长不小于d(其中d为不小于3的整数),则ξ(G)≤2,即γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的. 相似文献