1,720,978 research outputs found
On the Oberwolfach problem for single-flip 2-factors via graceful labelings
Full text linkLet F be a 2-regular graph of order v. The Oberwolfach problem OP(F), posed in 1967 and still open, asks for a decomposition of Kv into copies of F. In this paper we show that OP(F) has a solution whenever F has a sufficiently large cycle which meets a given lower bound and, in addition, has a single-flip automorphism, which is an involutory automorphism acting as a reflection on exactly one of the cycles of F. Furthermore, we prove analogous results for the minimum covering version and the maximum packing version of the problem. We also show a similar result when the edges of Kv have multiplicity 2, but in this case we do not require that F be single-flip. Our approach allows us to explicitly construct solutions to the Oberwolfach Problem with well-behaved automorphisms, in contrast with some recent asymptotic results, based on probabilistic methods, which are nonconstructive and do not provide a lower bound on the order of F that guarantees the solvability of OP(F). Our constructions are based on a doubling construction which applies to graceful labelings of 2-regular graphs with a vertex removed. We show that this class of graphs is graceful as long as the length of the path-component is sufficiently large. A much better lower bound on the length of the path is given for an α-labeling of such graphs to exist
Constructing uniform 2-factorizations via row-sum matrices: Solutions to the Hamilton-Waterloo problem
No full textIn this paper, we formally introduce the concept of a row-sum matrix over an arbitrary group G. When G is cyclic, these types of matrices have been widely used to build uniform 2-factorizations of small Cayley graphs (or, Cayley subgraphs of blown-up cycles), which themselves factorize complete (equipartite) graphs. Here, we construct row-sum matrices over a class of non-abelian groups, the generalized dihedral groups, and we use them to construct uniform 2-factorizations that solve infinitely many open cases of the Hamilton-Waterloo problem, thus filling up large parts of the gaps in the spectrum of orders for which such factorizations are known to exist
On the minisymposium problem
Full text linkThe generalized Oberwolfach problem asks for a factorization of the complete graph K-v into prescribed 2-factors and at most a 1-factor. When all 2-factors are pairwise isomorphic and v is odd, we have the classic Oberwolfach problem, which was originally stated as a seating problem: given v attendees at a conference with t circular tables such that the ith table seats ai i people and Sigma(t)(i=1) a(i) = v, find a seating arrangement over the v-1/2 days of the conference, so that every person sits next to each other person exactly once.In this paper we introduce the related minisymposium problem, which requires a solution to the generalized Oberwolfach problem on v vertices that contains a subsystem on m vertices. That is, the decomposition restricted to the required m vertices is a solution to the generalized Oberwolfach problem on m vertices. In the seating context above, the larger conference contains a minisymposium of m participants, and we also require that pairs of these m participants be seated next to each other for (sic)m-1/2(sic) of the days.When the cycles are as long as possible, i.e. v, m and v - m, a flexible method of Hilton and Johnson provides a solution. We use this result to provide further solutions when v equivalent to m equivalent to 2 (mod 4) and all cycle lengths are even. In addition, we provide extensive results in the case where all cycle lengths are equal to k, solving all cases when m | v, except possibly when k is odd and v is even
The Hamilton–Waterloo Problem with even cycle lengths
No full textThe Hamilton–Waterloo Problem HWP(v;m,n;α,β) asks for a 2-factorization of the complete graph K_v or K_v −I, the complete graph with the edges of a 1-factor removed, into α C_m-factors and β C_n-factors, where 3 ≤ m < n. In the case that m and n are both even, the problem has been solved except possibly when 1 ∈ {α,β} or when α and β are both odd, in which case necessarily v ≡ 2 (mod 4). In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to HWP(v;2m,2n;α,β) for odd α and β whenever the obvious necessary conditions hold, except possibly if β=1; β=3 and gcd(m,n)=1; α=1; or v=2mn∕gcd(m,n). This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above
- …
