共查询到19条相似文献,搜索用时 62 毫秒
1.
吕洪升 《安徽工程科技学院学报:自然科学版》2009,(2)
Hamilton临界图Cm,n是一个重要图类,当其中的某些参数、边的关联方式或边的数量等发生变化时,将产生一个新的有趣图类C′m,n(称为Cm,n的派生图类),通过对图类C′m,n的Hamilton性的讨论,得出了图类C′m,n存在Hamilton圈的充要条件. 相似文献
2.
用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得对所有的1≤i≤r都满足Hi Gi,则称图G对于(H1,H2,…,Hr)可r着色.R am sey数R(H1,H2,…,Hr)是使得完全图Kn对于(H1,H2,…,Hr)不可r着色的最小正整数n.令m1>m2≥m3,E r.do.s等给出了当m1足够大时R(Cm1,Cm2,Cm3)的值.通过对m1不是足够大的情况进行研究,证明了当m≥5时,R(Cm,C3,C3)=5m-4;并给出了当m1≤7时R(Cm1,Cm2,Cm3)的值. 相似文献
3.
讨论两个有向圈Cn与Cm的卡氏积图Cn×Cm的Hamilton性,给出并证明了:Cn×Cm存在有向Hamilton路,但未必存在有向Hamilton圈;当n|m时,Cn×Cm必存在有向Hamilton圈. 相似文献
4.
用r种颜色对图G的所有边着色,记着第i色的边构成的子图为G1,如果存在一种着色方法使得对所有的1≤i≤r都满足Hi¢Gi,则称图G对于(H1,H1,….Hr)可r着色.Ramsey数尺(H1,H2,…,Hr)是使得完全图Kn对于(H1.H2,…,Hr)不可r着色的最小正整数n,令m1〉m2≥m3,Erdoes等给出了当m1足够大时R(Cm1,Cm2,Cm3)的值.通过对m1不是足够大的情况进行研究,证明了当m≥5时,R(Cm,C3m,C3)=5m=4;并给出了当m1≤7时R(Cm1,Cm2,Cm3)的值. 相似文献
5.
对一个正常边染色满足相邻点的色集不同,称为邻强边染色,其所用最少染色数称为邻强边色数.就圈Cm与星K1,n的联图CmVK1,n,文章中得到了在m,n不同取值情况下的邻强边色数. 相似文献
6.
两类2连通(n,n+4)图的色唯一性 总被引:1,自引:1,他引:0
2连通的(n,n 4)图是有n个顶点n 4条边的连通图,利用图的色多项式理论研究了两类2连通的(n,n 4)图的色性,由此部分或完全解决了图G5和图G12的色唯一性问题. 相似文献
7.
一个图称为[s,t]-图,如果它的任意s阶导出子图中至少含有t条边.用Gn表示任意n阶图.文章证明了n-连通的[n+2,n]-图是Hamilton图或同构于Kn+1^c∨Gn 相似文献
8.
以Gn,n 3表示n点n 3边2-连通的图,将图族Gn,n 3分为17种互不同胚的图族,并根据色多项式系数将这些图分为互不色等价的5类.利用相关的色多项式公式以及色等价定理,证明了一类2-连通(n,n 3)-图在一定条件下是色惟一的. 相似文献
9.
设G=(V,E)是一个具有m条边的n阶简单图,γ(G)是图G的无符号拉普拉斯谱半径。本文利用图的无符号拉普拉斯谱半径讨论了图的Hamilton性,并分别给出了一个图包含Hamilton路以及泛圈图的充分条件。 相似文献
10.
林泓 《集美大学学报(自然科学版)》2010,15(6)
若图G包含一个经过G的每个顶点的圈,则称图G为Hamilton图.若一个连通图G有n条独立边,且任意n条独立边都可扩展为G的完美匹配,则称G为n-可扩图.利用判别Hamilton图的Fan-型条件和Chvatal-Erdos型条件,分别得到两个新的判别n-可扩图的充分条件. 相似文献
11.
令Cm,n表示长为m的圈与n个孤立点的联结(join)所得的图. 本文证明了Cm,n的最小亏格和最小不可定向亏格与完全二部图Km,n的相等. 同时,证明当m≥2并且n≥2时, Km,n在其最小可定向曲面上有一个强嵌入; 当m≥3并且n≥3,时, 在最小不可定向曲面上有一个强嵌入. 相似文献
12.
针对离散数学课程教学面临的一些问题,以哈密尔顿图教学内容为例,讨论了教学中的三个问题,以达到理解教学内容、引发思考、提高自主探索能力的目的。 相似文献
13.
陈婵 《杭州师范学院学报(自然科学版)》2001,(4)
Goodey证明每个三正则 3连通的面度全为 4或全为 6的平面图都是 Hamilton图 ,本文探讨四正则平面图与其对偶图的 Hamilton圈 相似文献
14.
Hamilton圈问题是一个典型的NP-完全问题,文章设计和研究了闭包是完全图的求Hamilton圈的新算法,其基于Bondy-Chvátal算法,与原来算法相比,新算法存在易于程序设计、可读性强等优点,且不失其好算法的特性。 相似文献
15.
16.
完全二部图K5,n的点可区别IE-全染色 总被引:2,自引:0,他引:2
设G是简单图,图G的一个k-点可区别IE-全染色(简记为k-VDIET染色)f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,且满足:A↓uv∈E(G),有f(u)≠f(v);A↓u,v∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE-全色数。 相似文献
17.
田京京 《兰州理工大学学报》2010,36(4)
对简单连通图G(V,E),存在一个正整数k,和映射f:V(G)∪E(G)→{1,2,…,k},使得对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,而χvate(G)=min{k|k-AVD-VETC},称为G的邻点可区别VE-全色数,其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}.给出圈的倍图D(Cm)和扇的倍图D(Fm)的邻点可区别VE-边全色数. 相似文献
18.
完全二部图K5,n的点可区别IE全染色 总被引:1,自引:1,他引:0
设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到{1,2,…,k}的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。 数min{k|G有一个k VDIET染色}称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。 相似文献
19.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图n∪i=1∧C4,mi是优美图,且是交错图. 相似文献