首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
图的顶点魔幻全标号指:对于图G(p,q),任意顶点v及其关联边的标号值之和等于常数k,其中标号值集合与集合{1, 2,…,p+q}一一映射.该文实现了一种针对随机图的顶点魔幻全标号优化算法,能够求解得到有限点内简单连通图的标号,通过结果分析,发现了两类太阳图Sn和GSn、广义太阳图Sn,m以及图P(n, 1)的标号特性,总结出若干定理并给出证明.  相似文献   

2.
G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.  相似文献   

3.
图G是3-边连通的且G的奇度点的数目为k.若k小于等于4,则G是上可嵌入的; 若k大于等于6,则ξ(G)小于等于k/2减去1.而且当k不小于6时,存在无限多个3边连通图G使得ξ(G)等于k/2减去1.  相似文献   

4.
设计了一种算法,逐个求解有限点以内的所有简单连通图的(a,d )-边反幻点标号,然后根据标号结果给出了若干针对特殊图和联图的精确算法,针对一般图则给出了一个启发式搜索算法模型. 该算法分为两个部分,第一部分依据定义设置预判函数,对图集中的所有图进行预判,剔除部分无(a,d )-边反幻点标号的图;第二部分求解剩余图集的(a,d )- 边反幻点标号. 特别地,通过预判函数知,当q ≥ p 时,图G ( p,q ) 无(a,2)-边反幻点标号,故利用算法得到了13 个点以内所有树图的(a,2)-边反幻点标号.  相似文献   

5.
本文采用[1]或[2]的术语和记号.称最小度为δ且连通度为k的p阶简单图为(p,δ,k)图,称最小度为δ且棱数为q,?的p阶简单图为δ度上准正则图,其度为δ 1的顶点称为上奇点.图H_(p,δ,k)表示上准正则(p,δ,k)图,G=H_(p,δ,k)表示G是图H_(p,δ,k).Harary曾就p>δ=k≥2作出图H_(p,δ,k).今用图H_(p,δ)记这类图,并用图H_(p,0)记p阶空图,图H_(p,1)记p阶1度上准正则图.  相似文献   

6.
设G是连通图,G的k阶幂图Gk是一个与G具有相同顶点集的图,Gk中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图Pnk的点连通度κ(Pnk)、边连通度λ(Pnk)和限制边连通度λ2(Pnk).得到:当n>k时,κ(Pnk)=λ(Pnk)=k;关于限制边连通度:当2≤n≤k+1时λ2(Pnk)=2n-4,当n>k+1时,λ2(Pnk)=2k-1.  相似文献   

7.
称有限群G的Cayley图Γ是正规Cayley图,如果G的右正则表示R(G)Aut(Γ).该文主要证明了2p2q 2阶二面体群连通3度Cayley图的正规性,其中p>q均为奇素数.作为应用,还证明了Aut(Γ)是可解群.  相似文献   

8.
设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

9.
定义并确定了两种类型的图:当n(≥2)阶的连通图的所有k(≥2)阶连通诱导子图均为非奇异时,称其为完美非奇异图;当n(≥3)阶连通图的所有k(≠2)阶连通诱导子图均为奇异时,称其为完美奇异图.  相似文献   

10.
一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.  相似文献   

11.
讨论非连通图C_(4m)∪G的优美性,再次对非连通图C_(4m)∪G的优美标号,给出了非连通图C_(4m)∪G是优美图的两个充分条件:非连通图C_(4m)∪G存在缺标号值k+4m的优美标号;当图G是特征为k且缺k+m标号值的交错图时,非连通图C_(4m)∪G存在缺标号值k+4m,特征为2m+k的交错标号。  相似文献   

12.
无爪图与分裂图的L(d,1)-T标号   总被引:1,自引:0,他引:1  
给定一个简单连通图G及其一棵支撑树T,图G的1个L(d,1)-T标号即一个标号函数g满足:①G的任意2个相邻点的标号至少差1;②T上任意两个相邻点的标号至少差d;③G上任意两个距离为2的点的标号至少差1.本文研究了无爪图与分裂图的L(d,1)-T标号并给出了Tld,T(G)一个界.  相似文献   

13.
非连通图C4m∪G 的优美标号   总被引:1,自引:0,他引:1  
讨论了非连通图C4 m∪G的优美性,给出了非连通图C4 m∪G是优美图的4个充分条件:当图G是缺标号值k+3 m且特征为k的交错图时,非连通图C4 m∪G存在着缺标号值k+1的优美标号;当图G是缺标号值k+m+1且特征为k的交错图时,非连通图C4 m∪G存在特征为2 m+k+1缺标号值k+1的交错标号;当图G是缺标号值k+2 m且特征为k的交错图时,非连通图C4 m∪G存在缺标号值k+3 m的优美标号;当图G是缺标号值k+2 m+1且特征为k的交错图时,非连通图C4 m∪G存在缺标号值k+m的优美标号。  相似文献   

14.
给出了二维可定向流形的几个定理。 (K6-E(K3) )不能三胞腔嵌入二维可定向流形 ;若围长为g的 (p ,q) -连通图能G 2 Sk,则g >3 ,q 3(p +2k - 2 ) ,q 2 (p+2h - 2 ) ;n点k -正则图G能三胞腔嵌入Sh,则h=1+n(k - 6 ) / 12。  相似文献   

15.
设G为有限无向简单图,G的邻接矩阵的特征值称为G的特征值,G的最大特征值称为G的谱半径.二分图的特征值在量子化学中有意义,因而研究二分图的特征值有重要的实用价值.K1^l,k(k≥l≥1)记星图K1.k的l个悬挂点各接出一条悬挂边所得的图.Tn(q)表示边无关数为q(≥5)的n阶树的集合.(1.1)T(q-3,n-2q 1)∈Tn(q)为K1^q-2,n-q-l的某个2度顶点上接出一条路P2所得的图.给出了Tn(q)中树的谱半径的第三大值。并证明了:当n-2q=1时,取得该值的唯一的树为K1^q,q;当n-2q≥2时,取得该值的树为(1,1)T(q-3,n-2q 1).  相似文献   

16.
本文的主要结果是在研究循环图结构的基础上,探讨了循环图连通的充要条件,进而证明了连通的循环图都是Hamilton图的一般结论。凡文中没有定义的概念及未加证明的结论,均可在文章[1]中见到。定义1 如果(n,i-1)=1,2≤7≤[(n+1)/2],则公式 k(i—1)+i(mod n),k∈数集Z,称为标号公式.如果(n,i-1)=m>1,那么矩阵 R={1 1+i-1 … 1+k(i-1)… 2 2+i-1 … 2+k(i-1)……………………………… m m+i-1 … m+k(i-1)…}m×n/m (mod n)可以给2—度循环图G标号,使其邻接矩阵为循环矩阵。R称为图G的标号矩阵,其中k按mod n/m来计算。  相似文献   

17.
简单图G的一个k-全标号λ:V∪E—→{1,2,…,k}称为点的全非正规k-标号,如果对于图G的任意两个不同的点x和y,它们的权wt(x)和wt(y)是不同的,其中图G的某个点x的权wt(x)是指点x的标号以及与x相关联的所有边的标号之和.图G的点的全非正规强度是使得G具有点的全非正规k-标号的最小正整数k,用tvs(G)表示.具有n个顶点的完全m-部图,如果它的每一部分或是具有[n/m]*个顶点,或是具有[n/m]*个顶点,则记为T_(m,n).本文给出了均匀完全7-部图T_7,n(n≠19)的全非正规强度.  相似文献   

18.
讨论了非连通图G23∪G的优美性,给出了非连通图G23∪G是优美图的两个充分条件.证明了如果图G是特征为k且缺k+2或k+11标号值的交错图,则非连通图G23∪G存在缺k+1标号值的优美标号.  相似文献   

19.
曹萌萌  孙磊 《山东科学》2011,24(4):69-72

本文给出了图的两个关于点的邻域限制标号的定义:非完全邻域限制标号SN(p,q)与完全邻域限制标号TN(p,q)。SN(p,q)标号是仅对图的大度点的邻域做限制的正常标号;TN(p,q)标号是对图的所有点的邻域做限制的正常标号。图G的非完全邻域限制标号数与完全邻域限制标号数分别记为SLp,q(G),TLp,q(G)。本文主要给出了某些图G的SLp,q(G),TLp,q(G)的界。  相似文献   

20.
本文讨论了如何对已知的 k=k(G)构造一个 n 阶的具有最多边数的极小 k—连通图,同时得出了极小 k—连通图的边数的上界.如果 k 1相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号