共查询到20条相似文献,搜索用时 62 毫秒
1.
设图G为一简单图,顶点集为V(G),边集为E(G),G的线图为L(G),如果一个图G满足κ(G)≥α(G)或dia(G)≤2,则它的线图L(G)为哈密顿的,在相同条件下,本文考虑L(G)中2-因子的分支数. 相似文献
2.
利用全图的性质研究图的全色数.给出正则图及其补图的全色数之间的关系。得到:若 G 是 k-正则图(2≤k相似文献
3.
设G=(V,E)为n阶简单连通图,若对每一个k(3≤k≤n),都含有长度为k的圈Ck,则称G为泛圈图。本文主要利用图及其补图的Wiener指数、hyper-Wiener指数,给出具有最小度条件的简单连通图是泛圈图的充分条件。 相似文献
4.
自补图的L(2,1)-标号 总被引:1,自引:1,他引:0
研究自补图G的L(2,1)-标号问题,证明了自补图的L(2,1)-标号数满足λ(G)≤2△。验证了关于一般图的L(2,1)-标号数的猜想λ(G)≤△2对于自补图的正确性。 相似文献
5.
图G存在Pk因子,如果G有一个支撑子图H使得H的每个分支都是一条恰含k个顶点的路,其中k≥3.图G存在K1,n因子,如果G有一个支撑子图H使得H的每个分支都是含n+1个顶点的星,其中n≥1.首先给出了一个关于图G中存在Pk因子的必要条件,并给予证明.在此基础上,得到G的线图中存在Pk因子的必要条件.此外,得到了Hall... 相似文献
6.
循环图C_(2n)(1,3)的2-偶匹配可扩性 总被引:1,自引:0,他引:1
设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的. 相似文献
7.
赵炳新 《山东大学学报(理学版)》1991,(4)
圈C称为图G的支配圈,若对G中任一点v,至少有圈C上的一个顶点与之邻接.类似定义图G的支配路.本文讨论了图中支配圈和支配路的存在性,得到下列结果:(1)设G是有n个顶点,ε条边的k-连通图(k≥1),若ε>((n-k)/2)~2-(3n-k)/2+4,则G中存在支配圈.(2)设G是有n个顶点的k-连通图(k≥2),若对图G中任何有k个顶点的独立点集{v_0,v_1,…v_(k-1)},满足N(v_i)∩N(v~i)=φ(0≤i≠i≤k-1),有~(k-1)∑_(i=0)d(v_i)>n-2(k+2)成立,则G中存在支配路. 相似文献
8.
程志谦 《河南科技大学学报(自然科学版)》2001,22(3):92-94
利用Whitnoy的著名结果 :P(G ,λ) = n - 1i =1 (- 1) ibiλn -i给出并证明了 :①G为连通偶图 ,当bn -1为奇数 ;②G为树 ,当bn -1=1;③分支数为k的图是偶图 ,当bn -k是奇数且bi=0 (n -k +1≤i≤n - 1)等八个定理 相似文献
9.
令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树. 相似文献
10.
图与其补图谱半径之和的新上界 总被引:9,自引:0,他引:9
该文给出了图与其补图谱半径之和ρ(G)+ρ(Gc)的新上界,对任一n阶图G,有:p(G)+p(GC)≤((2-1/t)n(n-1))和p(G)+p(GC)≤((2-1/T)n(n-1))其中t=min{k,(k-)},T=max{k,(k-)},k,(k-)分别为图G和其补图Gc的色数.从而改进了[6],[8],[10]的结果. 相似文献
11.
12.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图. 相似文献
13.
关于Km,n并图的优美性 总被引:2,自引:0,他引:2
对于自然数k,m,n,本文给出一类非连通图↑k∪↓i=1Kmi.ni;通过构造标号函数的方法,证明了当max{mi,ni}≥3,min{mi,ni}≥2(i=1,2,…,k)时这类图既是优美图,也是交错图;从而给出构造一类任意个图的并图是优美图的一种方法,拓宽了优美图及其应用的道路。 相似文献
14.
15.
再论图Pn^3的优美性 总被引:3,自引:0,他引:3
给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的. 相似文献
16.
17.
田子红 《兰州大学学报(自然科学版)》2002,38(6):6-13
设λKv是λ重V点完全图,G为一个无弧立点的有限简单图,λKv的一个G-覆盖设计,记为(v,G,λ)-CD,是指一个对子(X,D),其中X为点集,D为λKv的一些子图(亦称为区组)构成的集合,使得任一区组均与G同构,且任意两个不同点组成的边至少在D的λ个区组中出现,讨论了两类六点七边图Gi=K2,3 e(i=1,2)的最优覆盖的存在性问题,证明了存在(v,Gi,λ)-OCD,i=1,2当且仅当v≥6,除去非最优(但为最大)的C(6,G1,1)=4。 相似文献
18.
图K2,3+e的最优填充的存在性 总被引:1,自引:0,他引:1
田子红 《河北师范大学学报(自然科学版)》2002,26(4):333-337
讨论了2类6点7边图Gi=K12,3+e(i=1,2)的最优填以存在性问题,证明了:存在(v,Gi,λ)-OPD当且仅当v≥6,除去非最优的P(6,Gi,1)=1及未知的(9,Gi,1)-OPD,i=1,2。 相似文献
19.
20.