Search

Abstract: Given a combinatorial design D with block set B, the block‐intersection graph (BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | > 0. The i‐block‐intersection graph (i‐BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | = i. In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes. [ABSTRACT FROM AUTHOR]

Let G = K ( n 0 , … , n p − 1 ; λ 1 , λ 2 ) be the graph with p parts V 0 , V 1 , … , V p − 1 of n 0 , … , n p − 1 vertices, respectively, where there are λ 1 edges between each pair of vertices from the same part and λ 2 edges between each pair of vertices from distinct parts. A holey hamilton cycle of deficiency V i of G is a hamilton cycle of G − V i for some i satisfying 0 ≤ i ≤ p − 1 . A holey hamiltonian decomposition is a set of holey hamilton cycles whose edges partition E ( G ) . Representing each (holey) hamilton cycle as a color class in an edge-coloring, a (holey) hamiltonian decomposition of G is said to be fair if between each pair of (not necessarily distinct) parts the (permitted) color classes have size within one of each other—so the edges between a pair of parts are shared “evenly” among the (permitted) color classes. Similarly, a (holey) factorization of G is said to be internally fair if within each color class the edges between vertices of distinct parts are shared evenly among all pairs of distinct parts (for which that color class is permitted), and if within each color class the edges joining vertices from the same part are shared evenly among all parts (for which that color class is permitted). In this paper the existence of fair hamiltonian and fair holey hamiltonian decompositions of G are each settled except in a few cases. Simultaneously we settle the existence of internally fair and internally fair holey hamiltonian decompositions of G in a slightly more general setting. [ABSTRACT FROM AUTHOR]