Almost Resolvable Maximum Packing of Complete Graphs with5-Cycles

【作者】 周敏；

【导师】 曹海涛；

【作者基本信息】 南京师范大学 ， 运筹学与控制论， 2014， 硕士

【摘要】 设X为完全图Kn的点集.k-圈填充是一个三元组(X,C,L),其中C是完全图中边不交的k-圈集合,L是Kn的边集的子集,L中的边不属于C中任何一个k-圈.k-圈填充的几乎平行类是由[n/k]个点不交的k-圈组成的集合.当n≡0(mod k)时,几乎平行类就称为平行类.当集合C可以划分成若干个几乎平行类时,k-圈填充(X,C,L)称为几乎可分解的.几乎可分解的k-圈填充(X,C,L),在相同的参数条件下,若几乎平行类个数最大时,称为可分解的最大k-圈填充,记为k-RMCP(n).令D(n,k)表示k-RMCP(n)中几乎平行类的个数.当k=4时,D(n,k)已经被Billington等人解决了.除了一些可能的例外,当n≡k(mod2l)并且k≡1(mod2)或n≡1(mod2k)且k∈{6,8,10,14}∪{m:5≤m≤49,m≡1(mod2)}时,D(n,k)也已经被Niu等人解决了.本文章将确定对所有的正整数n≥5,D(n,5)的值.更多还原

【Abstract】 Let X be the vertex set of Kn. A k-cycle packing of Kn is a triple (X, C, L), where C is a collection of edge disjoint k-cycles of Kn and L is the collection of edges of Kn not belonging to any of the k-cycles in C. An almost parallel class of a k-cycle packing of Kn is a collection of [n/k] vertex disjoint l-cycles. When n≡0(mod k), an almost parallel class is said to be a parallel class. A k-cycle packing (X, C, L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of Kn, denoted by l-RMCP(n), is a resolvable k-cycle packing of Kn (X, C, L) in which the number of almost parallel classes is as large as possible.Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k=4has been decided by Billington et al. recently. When n≡k (mod2k) and k≡1(mod2)or n≡1(mod2k) and k∈{6,8,10,14}∪{m:5≤m≤49, m≡1(mod2)}, D(n, k) also has been decided by Niu et al. with few possible exceptions. In this paper, we shall decide D(n,5) for all values of n≥5.更多还原