共查询到20条相似文献,搜索用时 234 毫秒
1.
设Sn是具有n个顶点各等长圈数不超过2的简单图的集合.若Sa中不存在图G'使|E(G')|〉|E(G)|,则称G是简单的最大圈分布(2)图(简记为简单MCD(2)图).用f*(n,2)表示具有n个顶点的简单MCD(2)图的边数.证明了对每个整数11≤n≤14,有f*(n,2)=n+[1/2(√11n-20 -2)],其中[a]是小于等于a的最大整数。 相似文献
2.
施永兵 《上海师范大学学报(自然科学版)》2000,29(4):9-12
令Sn是具有n个顶点没有两个等长圈的简单图的集合,若Sn中不存在图G′使│E(G′)│>│E(G)│,则称图G是简单MCD图,若简单MCD图G是2连通的,则称G是2连通简单MCD图,若G中一条路P的两个内点u都有dG(v)=2,则称P为G的简单路,一个2连通可平面图G称为广义多边形路,如果用下述方法得到图G是路,对应于G的每个内部面f(G-是G的平图)有一个G*的顶点f*,G*的两个顶点f*和g*,在G*中相邻当且仅当G-中相应的两个内部面的边界交于一条G-的简单路,作者证明了下述结果,当且仅当n∈{10,11,14,15,16,21,22}时,存在n个顶点的非广义多边形路的2连通简单MCD图。 相似文献
3.
具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图. 相似文献
4.
周后卿 《邵阳学院学报(自然科学版)》2011,8(1):5-7
设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))~(1/2))]+((2p-1)~(1/2))+1. 相似文献
5.
设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。 相似文献
6.
7.
图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法. 相似文献
8.
徐士达 《上饶师范学院学报》1992,(6)
一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。 相似文献
9.
索南仁欠 《辽宁师范大学学报(自然科学版)》2008,31(1):15-16
设Pn和Sn分别表示有n个顶点的路和星图,φ*(n,k 1)表示Pn 1的一个1度点与Sk 1的k个1度点邻接后得到的图,本文根据优美图的定义,就φ*(n,k 1)的顶点集和边集,构造了与非负整数集间的两种映射(单射和双射)关系,从而证明了特殊图φ*(n,k 1)是优美图. 相似文献
10.
《西北大学学报(自然科学版)》2015,(3):345-351
设Pn和Cn是具有n个顶点的路和圈,Sn是n个顶点的的星图,n G表示n个图G的无公共点的并。当m≥3是奇数时,图PSm+2-1(m+1)r是表示把2-1(m+1)Sr+1的每个分支的r度顶点分别与Pm的下标为奇数的2-1(m+1)个顶点重迭后得到的图,把图PS(2m+1)+(m+1)r中的两个r+1度顶点与2P3中的每个分支的一个2度点分别重迭后所得到的图为Ψ*(2,2,(2m+1)+(m+1)r),当m≥3是偶数时的此图记为Ψ*(2,2,(2m+1)+mr)。运用图的伴随多项式的性质,讨论了图簇Ψ*(2,2,(2m+1)+(m+1)r)∪K1和Ψ*(2,2,(2m+1)+mr)∪Sr+1的伴随多项式的因式分解式,若m=2kq-1,λn=(2nq-1)+2n-1qr,讨论了图簇Ψ*(2,2,λn)和Ψ*(2,2,λn)∪(n-1)K1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。 相似文献
11.
12.
13.
设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。 相似文献
14.
15.
设图G的顶点集为V(G),边集为E(G),g和f是定义在V(G)上的2个整值函数,满足对于一切x∈V(G),g(x)≤f(x).若G是一个(mg+rn,mf-rn)-图,1≤n<m,r≥2,且对于x∈V(G),有g(x)≥k≥1,则存在G的一个子图G′,使得G′具有一个(f,g)-因子(n,r)-正交于G的任意给定子图H,其中|E(H)|=nk. 相似文献
16.
关于几类特殊图的Mycielski图的邻点可区别全色数 总被引:8,自引:6,他引:2
设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数. 相似文献
17.
设G=(V1,V2;E)是一个二分图,其顶点数目满足|V1|=|V2|=n≥(k+1)s+1,s和k是满足s≥3并且k≥1的两个正整数. 定义σ1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ1,1(G)≥2[(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s. 相似文献
18.
李建湘 《邵阳学院学报(自然科学版)》2001,14(3):167-169
设G是一个n阶图,a和b是整数使得1≤a<b.设H是G的具有m条边的匹配,δ(G)是最小度.证明了若δ(G)≥a+1,n≥2(a+b)(a+b-1)/b,并且对G的任意两个不相邻的点x和y都有|NG(x)U
NG(y)|≥an/(a+b)+2,则G有[a,b]-因子F使得E(H)nE(F)= 相似文献
19.
设k为正整数,G是阶n≥2k的无三角形图。如果G中每一对不相邻的点u,v满足|N(u)∩N(v)|≥k+1,则G是超级-λk的,或者G≌Kk+1,n-k-1。这一结果在网络可靠性分析中有一定应用。 相似文献
20.
在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk,使得对于1ik,都有|V(Pi)|=ai并且vi是路Pi的一个端点. 相似文献