Hamiltonicity and restricted block-intersection graphs of -designs |
| |
Authors: | David A Pike Robert C Vandell Matthew Walsh |
| |
Institution: | aDepartment of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada, A1C 5S7;bDepartment of Mathematical Sciences, Indiana University–Purdue University, Fort Wayne, Indiana 46805-1499, USA |
| |
Abstract: | Given a combinatorial design with block set , its traditional block-intersection graph is the graph having vertex set such that two vertices b1 and b2 are adjacent if and only if b1 and b2 have non-empty intersection. In this paper, we consider the S-block-intersection graph, in which two vertices b1 and b2 are adjacent if and only if |b1∩b2| S. As our main result, we prove that {1,2,…,t−1}-block-intersection graphs of t-designs with parameters (v,t+1,λ) are Hamiltonian whenever t 3 and v t+3, except possibly when (v,t) {(8,5),(7,4),(7,3),(6,3)}. |
| |
Keywords: | Block designs Block-intersection graphs Hamilton cycles |
本文献已被 ScienceDirect 等数据库收录! |
|