共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
利用图的匹配多项式及其最大实数根的性质证明了图簇T(1,6,n)∪(∪i=0^sCpi)及补图匹配唯一的充要条件是n≠6,9,17,或n=7,Pi≠7. 相似文献
3.
设G是一个简单图,M(G;W)是由Farrell引进的G的匹配多项式,若对任何图H,M(G;W)=M(H;W)导出G同构于H,则称G是匹配唯一的。Farrell和Guo首先研究了圈和道路的匹配唯一性问题。本文研究具有度序列(4~1,2~(p-1))的图的匹配唯一性,得到了若干匹配唯一的图类。 相似文献
4.
讨论简单无向图G的匹配唯一性,利用匹配多项式的特征标、最大实数根及其代数性质证明了:当n≥1时,T(1,1,n,4,1)匹配唯一的充要条件是n≠1,4,7,解决了该类图的匹配唯一性. 相似文献
5.
完全三部图K(n-4,n,n)的色唯一性 总被引:1,自引:0,他引:1
邹辉文 《上海师范大学学报(自然科学版)》1998,(1)
设G是简单图,用P(G,λ)表示图G的色多项式.若对任意图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.用K(m,n,r)表示完全三部图,证明了当K=4时,如下猜想[1]成立:对非负整数n,k,当n≥k+2时,K(n-k,n,n)是色唯一图.即当n≥6时,K(n-4,n,n)是色唯一图. 相似文献
6.
设G=(x,y)是一个二部图,若|X+=|Y|,则称G是一个均衡二部图,文章证明了设G是2n阶均衡二部图,对任意正整数k≥2,若n≥4k-3,且最小度δ(G)≥n+2(k-1)/2,则任给G的一个完美匹配M,G中存在一个包含M的所有边的恰含k个分支的M-2-因子。 相似文献
7.
殷建 《山东大学学报(理学版)》2005,40(4):45-50,55
h(G,x)表示图G的伴随多项式,它从图G的补图出发研究色惟一和色等价.若P(G,λ):P(H,λ),称G和H色等价,一个图被称为是色惟一的,如P(G,λ)=P(H,λ)意味着G≈H.若h(G,x):h(H,x),称G和H伴随等价;G和H色等价当且仅当G^-和H^-伴随等价;G色惟一当且仅当G^-伴随惟一.Un表示从路Pn-4的每个1度点分别引出两个悬挂边所得到的具有两个3度点4个1度点的树.K4^-表示从K4中删去一条边得到的图.应用伴随多项式理论研究了图(UnUK4^-)^-的伴随多项式系数和根的性质,以此为基础刻画了图(UnUK4^-)^-的色等价图类。 相似文献
8.
设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G~H表示.令[G]={H\H~G).若[G]={G),称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2≤n1≤n2≤n3≤n4,得到了[G]С{K(x,y,z,w)-S|z y w =n1 n2 n3 n4,1≤z≤y≤z≤w≤n4-1,或1≤x≤y≤z≤n3-1和w=n4U{G},其中S是K(x,y,z,w)的某s条边组成的集合且K(x,y,z,w)-s表示从K(x,y,z,w)中删去S中所有边得到的图.从而证明了当n≥k 2,t≥2时,K(n-k,n,n,n)是色唯一的. 相似文献
9.
2《M(G)≤(√2+√5)的图G 总被引:3,自引:0,他引:3
马海成 《内蒙古大学学报(自然科学版)》2005,36(5):485-487
设肘(G)是图G的匹配多项式的最大根,由此刻画了2<M(G)≤√(2+√5)的图G。 相似文献
10.
王世英 《郑州大学学报(理学版)》2002,34(4):15-18,25
设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配,则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配,并令T=S-V(M)。对连通的非二部的n-可扩图G(n≥2),得到以下结果:(1)若r≤n且|T|≥2,则|V(G)|≥2(n r |T|--1)。(2)若r≤n-2且|T|≥2,则|V(G)|≥2(n r |T|)。(3)若|V(G)|≤4n-2,则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。 相似文献
11.
证明了图族m2P2∪m3P3∪[∪i≥2m2iP2i]∪dD4∪[∪j≥3njCj]∪tT1,2,3∪sT1,2,4匹配唯一。当且仅当dm2=dm3=n3t=n3n5s=n15t=n5n9s=mknk 1=0(k≥2),其中m2,m3,m2i(i≥2),d,nj(j≥3),t,s都是非负整数。 相似文献
12.
魏岭 《青海师范大学学报(自然科学版)》2004,(3):9-10
本文证明了图κK1∪m2P2∪m3P3∪[∪↑i≥2m2ipi]∪dD4∪tT1、2、3∪sT1、2、4匹配唯一当且仅当dm2=dm3=0,其中κ、m2、m3、m2i(i≥2)、d、t、s都是非负整数。 相似文献
13.
14.
申世昌 《宝鸡文理学院学报(自然科学版)》2008,28(2):86-87
目的讨论简单无向图的匹配等价问题。方法利用匹配多项式的定义和性质推导。结果给出了2个匹配等价定理。结论找到了大量的匹配等价图。 相似文献
15.
直径为2的无爪图的导出匹配可扩性 总被引:1,自引:0,他引:1
如果简单图G的每一个导出匹配都包含在它的一个完美匹配中,称图G是导出匹配可扩的,简称为IM-可扩的。研究了直径为2的无爪图的导出匹配性,证明了一个直径为2的无爪图G是IM-可扩的充分必要条件是:对任意满足|M|≤3的导出匹配M,G—V(M)没有奇分支。因而,直径为2的无爪图的IM-可扩性问题是多项式可解的。 相似文献
16.
17.
18.
19.
研究直径是2的图和直径是3的树的生成母图的导出匹配可扩性; 给出了一类导出匹配可扩的拟轮图, 并研究了直径是3的树加边的导出匹配可扩性. 相似文献
20.
宋文 《贵州大学学报(自然科学版)》1998,15(2):116-119
本文提出了一个串匹配的新算法,该算法适合于当主串与子串不存在许多“部分匹配”时的情况,它是对串匹配算法中,一般算法和KMP算法的补充。 相似文献