Paired many-to-many disjoint path covers of hypertori

详细信息    查看全文

• 作者：Brian G. Kronenthal ; ^{kronenthal@kutztown.edu} ; Wing Hong Tony Wong ^{wong@kutztown.edu}
• 关键词：Disjoint path covers ; Hypertorus ; Torus ; Flow Free
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：19 February 2017
• 年：2017
• 卷：218
• 期：Complete
• 页码：14-20
• 全文大小：385 K
• 卷排序：218

文摘

Let nn be a positive integer, and let d=(d1,d2,…,dn) be an nn-tuple of integers such that di≥2di≥2 for all ii. A hypertorus Qnd is a simple graph defined on the vertex set {(v1,v2,…,vn):0≤vi≤di−1 for all i}{(v1,v2,…,vn):0≤vi≤di−1 for all i}, and has edges between u=(u1,u2,…,un) and v=(v1,v2,…,vn) if and only if there exists a unique ii such that |ui−vi|=1|ui−vi|=1 or di−1di−1, and for all j≠ij≠i, uj=vjuj=vj; a two-dimensional hypertorus Q2d is simply a torus. In this paper, we prove that if d1≥3d1≥3 and d2≥3d2≥3, then Q2d is balanced paired 22-to-22 disjoint path coverable if both didi are even, and is paired 22-to-22 disjoint path coverable otherwise. We also discuss a connection between this result and the popular game Flow Free. Finally, we prove several related results in higher dimensions.