$K_v$的最大$K_2K_3$填充设计
Maximum $2\times 3$ Grid-Block Packings of $K_v$

DOI：10.3770/j.issn:2095-2651.2014.02.002

 作者 单位 王立冬 北京交通大学数学研究所, 北京 100044 中国人民武装警察部队学院基础部, 河北 廊坊 065000 刘红娟 廊坊职业技术学院计算机科学与工程系, 河北 廊坊 065000

令$K_v$表示$v$阶完全图, $G$表示不含孤立点的有限简单无向图.若$X$为$K_v$的顶点集,$\mathcal{A}$为$K_v$中与$G$同构的边不交的子图的集合,则称序偶$(X,\mathcal{A})$是一个$K_v$的$G$-填充,简记为$(v,G,1)$-填充. 当$G$为$K_2$和$K_3$的卡氏积时, 除去两个阶数外,对任意正整数$v$, 本文确定了$(v,G,1)$-填充中所含子图的最大个数.这种设计来源于在DNA文库筛选中的应用.

Let $K_v$ be the complete graph on $v$ vertices, and $G$ a finite simple undirected graph without isolated vertices. A $G$-packing of $K_v$, denoted by $(v,G,1)$-packing, is a pair $(X,\mathcal{A})$ where $X$ is the vertex set of $K_v$ and $\mathcal{A}$ is a family of edge-disjoint subgraphs isomorphic to $G$ in $K_v$. In this paper, the maximum number of subgraphs in a $(v,G,1)$-packing is determined when $G$ is $K_2\times K_3$, the Cartesian product of $K_2$ and $K_3$, leaving two orders undetermined. This design originated from the use of DNA library screening.