共查询到19条相似文献,搜索用时 46 毫秒
1.
关于图的代数连通度的注记 总被引:3,自引:1,他引:3
n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 . 相似文献
2.
3.
设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。 相似文献
4.
5.
设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质. 相似文献
7.
8.
设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. 相似文献
9.
讨论欧拉跳跃图,给出一个图是欧拉图,其跳跃图J(G)是欧拉图的充要条件及一个连通图G=(p,q)的跳跃图J(G)是欧拉图的充要条件,即定理1:设G=(p,q)是欧拉图,则J(G)是欧拉图当且仅当q≥5为奇数.定理2:设G=(p,q)是连通图,则J(G)是欧拉图的充要条件是⑴q≥5是奇数且q>ζ 1,每点的度有相同的奇偶性;⑵q≥6是偶数且q>ζ 1,任意一边的两端点的度有相异的奇偶性.其中ζ=max{d|u| d(v)|uv∈E(G)}. 相似文献
10.
潘登斌 《广西师范学院学报(自然科学版)》2002,19(3):5-6
在 Chartrand G.和 Lesniak关于图的线连通性定理的基础上 ,讨论了二分图的线连通度问题 ,得到这样一个结论 :若 G=( X,Y:E)是二分图 ,对任一对不相邻的点 u、v,d( u) + d( v) >[p/2 ],则λ( G) =δ( G) . 相似文献
11.
12.
证明若G是连通图,则J(G)≌G当且仅当G是G或Cor(K3).通过引进边度概念,讨论连通图G的跳跃图J(C)是Hamilton图的一些充分条件. 相似文献
13.
14.
颜荔融 《福州大学学报(自然科学版)》1992,(3):12-16
本文证实了Bondy的猜想.证明了:设 G为简单 3连通 3正则权图,|V(G)|=n>6,则G含圈C,使W(C)>4W(G)/n. 相似文献
15.
介绍了一类拟树所包含的Euler子图的个数,给出了简洁的计算公式,并进行了严格、详尽的证明.有关结果在理论物理的某些研究中具有重要的理论与应用价值。 相似文献
16.
17.
研究了全着色边临界图的结构,证明了对于△≥5的全着色边临界图G(V,E),若u∈V(G),d(u)=3,uvi∈E(G)(i=1,2,3),则△-1≤d(vi)≤△. 相似文献
18.
张卫标 《重庆工商大学学报(自然科学版)》2017,34(3):21-23
著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的. 相似文献
19.
文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数x (G)=△(G),点选择数xLV(G)=4,点边选择数xLVE(G)=△(G)+1. 相似文献