[1]王成敏,王荣荣.2×3格子区组填充和覆盖[J].南京师范大学学报(自然科学版),2017,40(03):13.[doi:10.3969/j.issn.1001-4616.2017.03.003]
　Wang Chengmin,Wang Rongrong.2×3 Grid-Block Packings and Coverings[J].Journal of Nanjing Normal University(Natural Science Edition),2017,40(03):13.[doi:10.3969/j.issn.1001-4616.2017.03.003]
点击复制

2×3格子区组填充和覆盖()
分享到：

《南京师范大学学报》（自然科学版）[ISSN:1001-4616/CN:32-1239/N]

卷:
第40卷
期数:
2017年03期
页码:
13
栏目:
·数学·
出版日期:
2017-09-30

文章信息/Info

Title:
2×3 Grid-Block Packings and Coverings
文章编号:
1001-4616(2017)03-0013-08
作者:
王成敏1; 王荣荣2
(1.泰州学院数理学院,江苏 泰州 225300)(2.江南大学理学院,江苏 无锡 214122)
Author(s):
Wang Chengmin1; Wang Rongrong2
(1.School of Science,Taizhou University,Taizhou 225300,China)(2.School of Science,Jiangnan University,Wuxi 214122,China)
关键词:
完全图; 格子区组填充; 格子区组覆盖
Keywords:
complete graph; grid-block packing; grid-block covering
分类号:
O157.2
DOI:
10.3969/j.issn.1001-4616.2017.03.003
文献标志码:
A
摘要:
一个r×c格子区组填充(或覆盖),是一个二元组(X,A),其中X为Kv的顶点集,A是Kv的一簇与Kr×Kc同构的子图(称为格子区组),满足Kv中每一条边至多(或至少)出现在某个子图中一次. 本文研究2×3格子区组填充和覆盖的存在性. 一方面,本文解决了最大2×3格子区组填充的两个可能例外,从而完全确立了最大2×3格子区组填充的存在性; 另一方面,本文基本解决了最小2×3格子区组覆盖的存在性.
Abstract:
A r×c grid-block packing(or covering),is a pair(X,A),where X is the vertice set of Kv,A is a set of subgraphs which are isomorphism to Kr×Kc(called grid-blocks),satisfying each edge of Kv occurs at most(or at least)once in certain subgraph. In this paper,the existence of 2×3 grid-block packing and covering is considered. We first completely determined the existence of maximum 2×3 grid-block packing by removing two possible exceptions. Then we almost completely determined the existence of minimum 2×3 grid-block covering with three possible exceptions.

参考文献/References:

[1] LI Y,YIN J,ZHANG R,et al. The decomposition of Kv into K2×K5’s[J]. Sci China Ser A,2007,50:1 382-1 388.
[2]ZHANG R,GE G,LING ALAN C H,et al. The existence of r×4 grid-block designs with r=3,4[J]. SIAM J Discrete Math,2009,23:1 045-1 062.
[3]BOLLOBAS B. Graph theory[M]. New York:Spriger-Verlag,1979.
[4]WEST D B. Introduction to graph theory[M]. Upper Saddle River:Prentice-Hall,1996.
[5]HWANG F K. An isomorphic factorization of the complete graph[J]. J graph theory,1995,19:333-337.
[6]DU D Z,HWANG F K. Pooling designs and nonadaptive group testing:important tools for DNA Sequencing[M]. Hackensack,NJ:World Scientic,2006.
[7]CARTER J E. Designs on Cubic Multigraphs[D]. Canada:McMaster University,1989.
[8]MUTOH Y,MORIHARA T,JIMBO M,et al. The existence of 2×4 grid-block designs and their applications[J]. SIAM J discrete Math,2003,16:173-178.
[9]MUTOH Y,JIMBO M,FU H L. A resolvable r×c grid-block packing and its application to DNA library screening[J]. Taiwanese J Math,2004,8:713-737.
[10]WANG L,LIU H. Maximum 2×3 grid-block packings of Kv[J]. Journal of mathematical research with applications,2014,34:137-146.
[11]COLBOURN C J,DINITZ J H. The CRC hankbook of combinatorial designs[M]. Boca Raton,FL:CRC Press,2007.
[12]BETH T,JUNGNICKEL D,LENZ H. Design theory[M]. Cambidge:Cambidge University Press.

备注/Memo

备注/Memo:
收稿日期:2017-01-16.
基金项目:国家自然科学基金(11471144)、江苏省自然科学基金(BK20171318).
通讯联系人:王成敏,博士,副教授,研究方向:组合设计理论及应用. E-mail:wcm@jiangnan.edu.cn
更新日期/Last Update: 2017-09-30