几类含圈图的全着色

对于图G=(V,E),一个正常全着色就是从V∪E到一个整数集的映射,使V∪E中的任意两个相邻或相关联的元素都着不同的颜色,图G=(V,E)的全色数xT(G)定义为xT(G)=min{k|存在G的一个正常k-全着急},本文对一类特殊图-含圈图的全着色给出了几个定理,验证了全着色猜想。

关于r-(P_0,…,P_(t-1))—泛圈图

若G中长为r+tj+i的圈恰好有Pi(0≤i≤t-1)个,其中r+tj+t-1≤n,j是P_0,…,P_(t-1)重复的次数,则称G为r-(P_0,…,P_(t-1))-泛圈图.主要采用构造法,给出当t=8时r-(P_0,…,P_7)-泛圈图的一些结果 .即设n≥14,≥6若2-3+-3≤n<2-2+-2且n-(r_((n,)-1))=s(mod8),s=0,1,…,7时,那么存在一个n阶r-(4,4,4,4,5,5,5,5)泛圈图,其中r=r_(0, λ)+s=﹛2^(λ-4)+3+s,当n≤3·2^(λ-4)+2时n-2^(λ-3)+1+s当n>3·2^(λ-4)+2时同时,利用类似的方法证明了r-(1,1,3,3,4,4,5,5)—泛圈图、r-(4,4,4,4,5,5,5,5)—奇(偶)泛圈图以及r-(1,1,3,3,4,4,5,5)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.

一类r-(d_(0),d_(1),…,d_(t-1))-泛圈图的结果

设r,t,j是正整数,若对每一个r+tj+i(r+tj+i≤n),n阶简单图G中长为r+tj+i的圈恰好有d_(i)个,0≤i≤t-1,其中t是d_(i)的周期数,j是t重复的次数,则称图G为r-(d_(0),…,d_(t-1))-泛圈图.主要讨论了r-(6·2^(μ_(1)),6·2^(μ_(1)),8·2^(μ_(1)),6·2^(μ_(1)))-泛圈图,r-(6·2^(μ_(1)),8·2^(μ_(1)),6·2^(μ_(1)),6·2^(μ_(1)))-奇(偶)泛圈图.

与泛圈图有关的一些结果

设r,t,j是正整数,对于n阶哈密顿图G,若对每一个r+tj+i(r+tj+i≤n),G中长为r+i+j的圈恰好有di个,0≤i≤t-1,其中t是di的周期,j是t重复的次数,则称图G为r-(d0,…,dt-1)-泛圈图.本文讨论了r-(3,3,4,3,4,3,3,3)-泛圈图,r-(3,5,5,3)-奇(偶)泛圈图,以及g(0,0,6,…,6)的界.

Minimum Coverings of Complete Directed Graphs with Odd Size Circuits

Let DKv denote the symmetric complete directed graph with v vertices, the covering number C(v,m) is a minimum number of covering DKv by m-circuits. In this paper, C(v,m) is determined for any fixed odd positive integer m and positive integer v, m ≤ v ≤ m + 6.