排序方式: 共有27条查询结果,搜索用时 15 毫秒
21.
完全三部图K(n- k,n,n)的色性 总被引:1,自引:1,他引:0
设P(G,λ)表示简单图G的色多项式;若对任意简单图H 满足P(H,λ) = P(G,λ),都有H 与G同构,则称G是色唯一图;设K(m ,n,r) 表示完全三部图;本文证明了:(1) 若n > k + k2/3,则图K(n - k,n,n) 是色唯一的,(2) 若n ≥8,则K(n - 4,n,n) 是色唯一的; 相似文献
22.
设G为简单图,P(G,λ)为G的色多项式。若对任意简单图H满足P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图,设K(m,n,r)表示完全三部图。证明了(1)对任意非负整数k,若n≥k+k^2/3,则K(n,n,n+k)是色唯;(2)若n≥4,则K(n,n,n+4)是色唯一图。 相似文献
23.
施永兵 《上海师范大学学报(自然科学版)》1995,(2)
设Sn是n个顶点的没有等长圈的简单图的集合.若G∈Sn且Sn中不存在图G'使|E(G')|>|E(G)|,则称图G是简单MCD图.若简单MCD图G是2连通的,则称G是2连通简单MCD图.本文证明了不存在具有28个顶点的含有同胚于K4的子图的2连通简单MCD图.于是结合DiscreteMath.126(1994),我们完全证明了下述定理:存在n个顶点的含有同胚于K4的子图的2连通简单MCD图当且仅当n∈{10,11,14,15,16,21,22}. 相似文献
24.
施永兵 《上海师范大学学报(自然科学版)》1998,(4)
用|V(G)|、|E(G)|和f(G)分别表示图G的顶点数、边数和圈数.设F(k)={f(G);G是满足|E(G)|-|V(G)|=k的无环连通图},n(k)=minF(k)和N(k)=maxF(k).证明了下述结果:(1)n(k)=k+1;(2)N(k)≤2k+1;(3)对每个整数k≥1,N(k)≥2k+k(k-1)+1且当1≤k≤4时等式成立;(4)对每个整数k≥1是奇数时,N(k)≥2k3;当k≥2是偶数时, 相似文献
25.
设r≥4且r是偶整数.阶为2n的偶图G被称为唯一r-偶泛圈图,如果对每个偶整数t,r≤t≤2n,G恰含一个长为t的圈,且G不含长小于,的圈.若G是唯一r-偶泛圈圈,则称G是r-UB-图.证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n+m的r-UB-图. 相似文献
26.
27.
设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)~(1/2)]且当3≤n≤10时等式成立。 相似文献