|Table of Contents|

2×3 Grid-Block Packings and Coverings(PDF)

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

Issue:
2017年03期
Page:
13-
Research Field:
·数学·
Publishing date:

Info

Title:
2×3 Grid-Block Packings and Coverings
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
PACS:
O157.2
DOI:
10.3969/j.issn.1001-4616.2017.03.003
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:
-
Last Update: 2017-09-30