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     

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     

Cyclic k‐cycle systems of order 2kn + k: A solution of the last open cases

We exhibit cyclic (K_v, C_k)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (K_v, C_k)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004.     

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     

A method to construct 1‐rotational factorizations of complete graphs and solutions to the oberwolfach problem

The concept of a 1‐rotational factorization of a complete graph under a finite group was studied in detail by Buratti and Rinaldi. They found that if admits a 1‐rotational 2‐factorization, then the involutions of are pairwise conjugate. We extend their result by showing that if a finite group admits a 1‐rotational ‐factorization with even and odd, then has at most conjugacy classes containing involutions. Also, we show that if has exactly conjugacy classes containing involutions, then the product of a central involution with an involution in one conjugacy class yields an involution in a different conjugacy class. We then demonstrate a method of constructing a 1‐rotational ‐factorization under given a 1‐rotational 2‐factorization under a finite group . This construction, given a 1‐rotational solution to the Oberwolfach problem , allows us to find a solution to when the ’s are even (), and when is an odd prime, with no restrictions on the ’s.     

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     

Some new results on 1‐rotational 2‐factorizations of the complete graph

It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph K_2n+1 under the action of a group G of order 2n is that the involutions of G are pairwise conjugate. Is this condition also sufficient? The complete answer is still unknown. Adapting the composition technique shown in Buratti and Rinaldi, J Combin Des, 16 (2008), 87–100, we give a positive answer for new classes of groups; for example, the groups G whose involutions lie in the same conjugacy class and having a normal subgroup whose order is the greatest odd divisor of |G|. In particular, every group of order 4t+2 gives a positive answer. Finally, we show that such a composition technique provides 2‐factorizations with a rich group of automorphisms. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 237–247, 2010     

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     

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     

Almost resolvable k‐cycle systems with

In this paper, we show that if and , then there exists an almost resolvable k‐cycle system of order for all except possibly for and . Thus we give a partial solution to an open problem posed by Lindner, Meszka, and Rosa (J. Combin. Des., vol. 17, pp. 404–410, 2009).     

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 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$.     

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     

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     

On the Enumeration of ‐Optimal and Minimax‐Optimal k‐Circulant Supersaturated Designs

In recent years, several methods have been proposed for constructing ‐optimal and minimax‐optimal supersaturated designs (SSDs). However, until now the enumeration problem of such designs has not been yet considered. In this paper, ‐optimal and minimax‐optimal k‐circulant SSDs with 6, 10, 14, 18, 22, and 26 runs, factors and are enumerated in a computer search. We have also enumerated all ‐optimal and minimax‐optimal k‐circulant SSDs with (mod 4) and . The computer search utilizes the fact that theses designs are equivalent to certain 1‐rotational resolvable balanced incomplete block designs. Combinatorial properties of these resolvable designs are used to restrict the search space.     

Decomposition of the complete graph plus a 1‐factor into cycles of equal length

We determine the necessary and sufficient conditions for the existence of a decomposition of the complete graph of even order with a 1‐factor added into cycles of equal length. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 170–207, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10019     

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.     

Exhaustive generation of k‐critical ‐free graphs

We describe an algorithm for generating all k‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P₇‐free graphs. We also prove that every P₁₁‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P₁₂‐free graph of girth at least five. Moreover, we show that every P₁₄‐free graph of girth at least six and every P₁₇‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001