ABSTRACT

As a special example of the candelabra systems (CQS), G-design is the extension of group divisible designs (GD), which plays an important role in quadruple systems’ construction. With application of Stern and Lenz’s result on one-factorization of graphs, by direct construction, it is given that the sufficient and necessary condition for the existence of the G-design with three groups is that.

Keywords:t-Designs, Quadruple Systems, Candelabra Systems, G-Design

三个组的G-设计

朱莉，王建

南通职业大学，江苏 南通

收稿日期：2015年11月2日；录用日期：2015年11月19日；发布日期：2015年11月26日

摘 要

G-设计是可分组设计(GD)的推广，同时又是烛台型设计(CQS)的特例，它在四元系设计中起到重要作用。文章应用Stern和Lenz关于图因子分解的结论，通过直接构造法，得到具有三个组的G-设计存在的充分必要条件：。

关键词 :t-设计，四元系，烛台型设计，G-设计

1. 引言

设和t是给定的正整数，G-设计(记为)是一个三元组(X, A, B)，其中X是一个元点集，A构成X的一个划分，B是X的一些子集组成的一个子集族，X的元素叫点，A的元素叫组，B的元素叫区组，满足(1)对任意，都有；(2)对任意，都有；(3)对任意与任意，都有；(4)对于X中每个t元子集T与任意，如果，则T恰好包含于B中个区组。时，记为。

当时，G-设计就是大家熟知的可分组设计或GD设计(参见[1] )。当时，G-设计是柄为0的烛台型四元系，而烛台型四元系在四元系中起到相当重要的作用(参见[2] )。Mills [3] [4] ，Hartman [5] [6] 研究了，得到了一些结论。当时，易知存在的充分必要条件是： (参见[4] )。本文讨论当时，的存在性。我们给出存在的充分必要条件是：。

文中用到的组合设计及图论方面的名词术语均参照著作[1] 和[7] 。

2. 预备知识

定理2.1存在的必要条件是：。

证明：中有个点，不同的三元点集共有个，其中能出现在区组中的有，而一个区组含有四个三元集，一个三元集可出现在个区组中，所以，中的区组数为，因而，。再设是设计中给定的点，能和组成三元集的点对共有个，其中能出现在区组中的有个，且每个三元集可出现在个区组中，而一个区组中能和组成三元集的点对有三个，所以，。综上两点，可得存在的必要条件是。

上述存在的必要条件可分类等价于以下四种情形

1)且或

2)且或

3)且或

4)且。

为证存在的充分性，我们需要图1-因子分解的有关知识。记G是具有个g点的图，其点集为。设，图G的边的差定义为和中小的一个。我们记图G的边的差为或，也即是

。

对于任何一个子集(表示不大于的最大整数)，我们定义是一个图，其点集为，边集为，即包含所有差属于的边。

图的一个子图如果包含了的全部点，则为的生成子图。如果图的一个生成子图是1-正则的，则称是的1-因子。如果图的边集可表示为它的某些1-因子的并，则称存在的1-因子分解，或称可1-因子化。下面的引理来自Stern和Lenz [8] ，我们在第3节的证明中将会用到，其中表示和的最大公约数。

引理2.2 (Stern和Lenz)如果包含一个元素使得是偶数，则图存在1-因子分解。

3. 主要结论

引理3.1如果存在，则对于任意正整数，存在。

证明：将的每个区组重复s倍，即得。

由引理2.1结合引理3.1，为证主要结论，我们只需考虑以下四种情形

1)且；

2)且；

3)且；

4)且。

引理3.2当时，存在。

证明：设，记所需设计的点集，组A：{： }。

区组B：{，，， }

(，，，)；

{，，， }

(由引理2.2，图存在1-因子分解，记是的1-因子分解，，)。

引理3.3当时，存在。

证明：设，记所需设计的点集，组A：{： }。

区组B：{，，， }

(，，，)重复4次；

{，，， }

(，，)重复2次；

{，，， }

(，，)重复2次；

{，，， }

(，，)重复2次；

{，，， }(，)；

{，，， }(，，)。

引理3.4当时，存在。

证明：设，记所需设计的点集，组A：{： }。

区组B：{，，， } (，，，)；

{，，， } (，，)；

{，，， } (，)。

引理3.5当时，存在。

证明：设，记所需设计的点集，组A：{： }。

区组B：{，，， }

(，，，)重复4次；

{，，， }

(，，，)重复2次；

{，，， }

(，，)重复2次；

{，，， }(，，)；

{，，， }(，，)

{，，， }(，)

定理3.6当时，存在。

证明：由引理3.2~3.5，结合引理3.1，可得存在的充分条件。

结合引理2.1和定理3.6，我们得到本文的主要结论。

定理3.7存在的充分必要条件是。

基金项目

国家自然科学基金项目(11171248和11371207)。

文章引用

朱莉,王建. 三个组的G-设计
G-Design with Three Groups[J]. 应用数学进展, 2015, 04(04): 365-368. http://dx.doi.org/10.12677/AAM.2015.44045

参考文献 (References)