Rotational k‐cycle systems of order v < 3k; another proof of the existence of odd cycle systems

We give an explicit solution to the existence problem for 1‐rotational k‐cycle systems of order v < 3k with k odd and v ≠ 2k + 1. We also exhibit a 2‐rotational k‐cycle system of order 2k + 1 for any odd k. Thus, for k odd and any admissible v < 3k there exists a 2‐rotational k‐cycle system of order v. This may also be viewed as an alternative proof that the obvious necessary conditions for the existence of odd cycle systems are also sufficient. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 433–441, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10061     

A complete solution to the existence problem for 1‐rotational k‐cycle systems of Kv

The necessary and sufficient conditions for the existence of a 1‐rotational k‐cycle system of the complete graph K_v are established. The proof provides an algorithm able to determine, directly and explicitly, an odd k‐cycle system of K_v whenever such a system exists. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 283–293, 2009     

Cyclic m‐cycle systems with m ≤ 32 or m = 2q with q a prime power

In this paper, the necessary and sufficient conditions for the existence of cyclic 2q‐cycle and m‐cycle systems of the complete graph with q a prime power and 3 ≤ m ≤ 32 are given. © 2005 Wiley Periodicals, Inc. J Combin Designs     

More results on perfect (3,3,6k + 4; 6k − 2)‐threshold schemes

A (2,3)‐packing on X is a pair (X, ), where is a set of 3‐subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. Its leave is a graph (X,E) such that E consists of all the pairs which do not appear in any block of . In this article, we shall construct a set of 6k ? 2 disjoint (2,3)‐packings of order 6k + 4 with K_1,3 ∪ 3kK₂ or G₁ ∪ (3k ? 1)K₂ as their common leave for any integer k ≥ 1 with a few possible exceptions (G₁ is a special graph of order 6). Such a system can be used to construct perfect threshold schemes as noted by Schellenberg and Stinson ( 22 ). © 2006 Wiley Periodicals, Inc. J Combin Designs     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

1‐rotationally resolvable 4‐cycle systems of 2Kv

In this article, it is shown that there exists a 1‐rotationally resolvable 4‐cycle system of 2K_υ if and only if υ ≡ 0 (mod 4). To prove that, some special sequences of integers are utilized. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 116–125, 2002; DOI 10.1002/jcd.10006     

Hamilton cycle decomposition of 6‐regular circulants of odd order

The circulant G = C(n,S), where , is the graph with vertex set Z_n and edge set . It is shown that for n odd, every 6‐regular connected circulant C(n, S) is decomposable into Hamilton cycles. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Group‐divisible designs with block size k having k + 1 groups,for k = 4, 5

We investigate the spectrum for k‐GDDs having k + 1 groups, where k = 4 or 5. We take advantage of new constructions introduced by R. S. Rees (Two new direct product‐type constructions for resolvable group‐divisible designs, J Combin Designs, 1 (1993), 15–26) to construct many new designs. For example, we show that a resolvable 4‐GDD of type g⁵ exists if and only if g ≡ 0 mod 12 and that a resolvable 5‐GDD of type g⁶ exists if and only if g ≡ 0 mod 20. We also show that a 4‐GDD of type g⁴m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 3 and 0 < m ≤ 3g/2, except possibly when (g,m) = (9,3) or (18,6), and that a 5‐GDD of type g⁵m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 4 and 0 < m ≤ 4g/3, with 32 possible exceptions. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 363–386, 2000     

Cyclic cycle systems of the complete multipartite graph

In this paper, we study the existence problem for cyclic $?$‐cycle decompositions of the graph $K_m\left[n\right]$, the complete multipartite graph with $m$ parts of size $n$, and give necessary and sufficient conditions for their existence in the case that $2?|\left(m?1\right)n$.     

Cyclically near‐resolvable 4‐cycle systems of 2Kv

Fu and Mishima [J. Combin. Des. 10 (2002), pp. 116–125] have utilized the extended Skolem sequence to prove that there exists a 1‐rotationally resolvable $4$‐cycle system of $2K_v$ if and only if $v\equiv 0$ (mod $4$). In this paper, the existence of a cyclically near‐resolvable $4$‐cycle system is discussed, and it is shown that there exists a cyclically near‐resolvable $4$‐cycle system of $2K_v$ if and only if $v\equiv 1$ (mod $4$).     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?1.     

Resolvable even‐cycle systems with a 1‐rotational automorphism

In this article, necessary and sufficient conditions for the existence of a 1‐rotationally resolvable even‐cycle system of λK_v are given, which are eventually for the existence of a resolvable even‐cycle system of λK_v. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 394–407, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10058     

A Characterization of the degree sequences of 2‐trees

A graph G is a 2‐tree if G = K₃, or G has a vertex v of degree 2, whose neighbors are adjacent, and G/ v is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and realizing degree sequences of 2‐trees. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008     

Irreducible 2‐fold cycle systems

In this paper, it is shown that for any pair of integers (m,n) with 4 ≤ m ≤ n, if there exists an m‐cycle system of order n, then there exists an irreducible 2‐fold m‐cycle system of order n, except when (m,n) = (5,5). A similar result has already been established for the case of 3‐cycles. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 324–332, 2006     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

1‐rotational k‐factorizations of the complete graph and new solutions to the Oberwolfach problem

We consider k‐factorizations of the complete graph that are 1‐rotational under an assigned group G, namely that admit G as an automorphism group acting sharply transitively on all but one vertex. After proving that the k‐factors of such a factorization are pairwise isomorphic, we focus our attention to the special case of k = 2, a case in which we prove that the involutions of G necessarily form a unique conjugacy class. We completely characterize, in particular, the 2‐factorizations that are 1‐rotational under a dihedral group. Finally, we get infinite new classes of previously unknown solutions to the Oberwolfach problem via some direct and recursive constructions. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 87–100, 2008     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

{2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only

An m‐cycle system (S,C) of order n is said to be {2,3}‐perfect provided each pair of vertices is connected by a path of length 2 in an m‐cycle of C and a path of length 3 in an m‐cycle of C. The class of {2,3}‐perfect m‐cycle systems is said to be equationally defined provided, there exists a variety of quasigroups V with the property that a finite quasigroup (Q, , \, /) belongs to V if and only if its multiplicative (Q, ) part can be constructed from a {2,3}‐perfect m‐cycle system using the 2‐construction (a a = a for all a ∈ Q and if a ≠ b, a b = c and b a = d if and only if the m‐cycle (…, d, x, a, b, y, c, …) ∈ C). The object of this paper is to show that the class of {2,3}‐perfect m‐cycle systems cannot be equationally defined for all m ≥ 10, m ≠ 11. This combined with previous results shows that {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only. © 2004 Wiley Periodicals, Inc.     

Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001