2 Auxiliary Designs
In order to establish our main result, we shall employ both direct and recursive constructions. In
this section, we shall define some terminology and describe some of the auxiliary designs to be
used in our constructions. For more detailed information on some of these related combinatorial
structures, the reader is referred to [41].
Let DK
n
1
,n
2
,...,n
h
be the complete multipartite directed graph with vertex set X = ∪
1≤i≤h
X
i
,
where X
i
(1 ≤ i ≤ h) are disjoint sets with |X
i
| = n
i
, v = Σ
1≤i≤h
n
i
, and where two vertices x
and y from different sets X
i
and X
j
are joined by exactly one arc from x to y and one arc from
y to x.
Let K be a set of positive integers and r < min{k : k ∈ K}. An r-fold perfect holey Mendelsohn
design (or r-fold perfect HMD) with block size in K is an order pair (X, A) where A is a set
of cyclically ordered subsets of X, called blocks, which form an arc-disjoint decomposition of
DK
n
1
,n
2
,...,n
h
with the property that for any integer t (1 ≤ t ≤ r) and any two vertices x and y
from different sets X
i
and X
j
, there is exactly one circuit c ∈ A such that the directed distance
along c from x to y is r. Each X
i
(1 ≤ i ≤ h) is called a hole (or group) of the design and the
multiset {n
1
, n
2
, . . . , n
h
} is called the type of the design. We denote the design by r-fold perfect
(v, K, 1)-HMD (or r-fold perfect K-HMD) and use an “exponential” notation to describe its type
in general: a type 1
i
2
r
3
k
. . . denotes i occurrences of 1 , r occurrences of 2, etc.
If K = {k} and r = k − 1, then an r-fold perfect (v, {k}, 1)-HMD is briefly denoted by
(v, k, 1)-HPMD (or k-HPMD).
A (v, k, 1)-HPMD of type 1
v
is essentially a (v, k, 1)-PMD. A (v, k, 1)-HPMD of type 1
v −n
n
1
is called an incomplete a perfect Mendelsohn design, denoted by (v, n, k, 1)-IPMD or more briefly
by k-IPMD(v, n).
We shall also make use of the concept of a holey Steiner pentagon system.
Let S be a set and H={S
1
, S
2
, . . . , S
n
} be a set of subsets of S. A holey Steiner pentagon
system (HSPS) having hole set H is a triple (S,H,B) where B is collection of pentagons, satisfying
the following properties:
1. Two vertices from same hole S
i
do not occur together in any pentagon of B,
2. two vertices from different holes S
i
and S
j
(i 6= j) are joined by a path of length 1 in exactly
one pentagon of B, and also by a path of length 2 in exactly one pentagon of B.
It is fairly well-known that the existence of a holey Steiner pentagon system (HSPS) of type
T implies the existence of a 5-HPMD of the same type T (see, for example, [17], and we shall
make good use of this association.
The following existence results for 5-HPMDs and 5-IPMDs will be very useful. Note that the
existence of a 5-HPMD of type 5
6
is essentially established in Lemma 3.2 of [5] in the form of
what is described as a 5-FPMD, and this was inadvertently omitted from the update given in
[10].
Theorem 2.1.
[17, 10, 5] The necessary condition for the existence of a 5-HPMD of type h
n
,
namely, n ≥ 5 and n(n − 1)h
2
≡ 0 (mod 5), is also sufficient, except possibly for the following
cases:
(1)
h ≡ 1, 3, 7 or 9 (mod 10), h 6= 3, and n ∈ {6, 10, 20};
(2)
h ∈ { 1, 13, 17, 19} and n = 15;
4
http://www.paper.edu.cn
剩余19页未读，继续阅读
weixin_38586186
- 粉丝: 9
- 资源: 943
我的内容管理
展开
最新资源
- AirKiss技术详解：无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验：位示图法管理磁盘空闲空间
- JSON详解：数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析：WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型：便捷管理与低成本优势
- 机器学习入门指南：从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS：优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso：加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战：轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
