1,721,011 research outputs found
The structure of 2-pyramidal 2-factorizations
No full textA 2-factorization of a simple graph is called 2-pyramidal if it admits an automorphism group G fixing two vertices and acting sharply transitively on the others. Here we show that such a 2-factorization may exist only if is a cocktail party graph, i.e., with I being a 1-factor. It will be said of the first or second type according to whether the involutions of G form a unique conjugacy class or not. As far as we are aware, 2-factorizations of the second type are completely new. We will prove, in particular, that admits a 2-pyramidal 2-factorization of the second type if and only if n ≡ 1 (mod 8)
Infinitely many cyclic solutions to the Hamilton-Waterloo problem with odd length cycles
Get PDFIt is conjectured that for every pair (l,m) of odd integers greater than 2 with m=1 (mod l), there exists a cyclic two-factorization of Klm having exactly (m-1)/2 factors of type lm and all the others of type ml. The authors prove the conjecture in the affirmative when l = 1(mod4) and m≥l2-l+1
Some Results on 1-Rotational Hamiltonian Cycle Systems
No full textA Hamiltonian cycle system of the complete graph on v vertices (briefly, a HCS(v)) is 1-rotational under a (necessarily binary) group G if it admits G as an automorphism group acting sharply transitively on all but one vertex. We first prove that for any integer n greatest or equal to 3, there exists a 3-perfect 1-rotational HCS(2n+1). This allows to get the existence of an infinite class of 3-perfect (but not Hamiltonian) cycle decompositions of the complete graph. Then we prove that the full automorphism group of a 1-rotational HCS under G is G itself unless the HCS is the 2-transitive one. This allows us to give a partial answer to the problem of determining which abstract groups are the full automorphism group of a HCS. Finally, we revisit and simplify by means of a careful group theoretic discussion, a formula by Bailey, Ollis, and Preece on the number of inequivalent 1-rotational HCSs under G. This leads us to a formula counting all 1-rotational HCSs up to isomorphism. Though this formula heavily depends on some parameters that are hard to compute, an imprtant lower bound for the number of non isomorphic 1-rotational (and hence symmetric) HCSs is obtained
3-pyramidal Steiner triple systems
Get PDFA design is said to be f-pyramidal when it admits an automorphism group fixing f points and acting sharply transitiveky on all the others. The problem of establishing the set of values of v for which there exists a f-pyramidal Steiner system of order v was deeply investigated in the case f=1 but it remains open for special classes of v. The same problem for the next class of f, which is f=3, is completly solved here. There exists a 3-pyramidal Steiner triple system of order v if and only if v=7,9,15 (mod 24) or v=3,19 (mod 48)
On the generalized Oberwolfach problem
No full textThe generalized Oberwolfach problem OP_t(2w + 1; N_1, N_2, ..., N_t; α_1, α_2, ..., α_t) asks for a factorization of K_{2w + 1} into α_i C_{N_i}-factors (where a C_{N_i}-factor of K_{2w + 1} is a spanning subgraph whose components are cycles of length N_i ≥ 3) for i = 1, 2, ..., t. Necessarily, N = lcm(N_1, N_2, ..., N_t) is a divisor of 2w + 1 and w = Σ_{i=1}^t α_i.
For t = 1 we have the classic Oberwolfach problem. For t = 2 this is the well-studied Hamilton-Waterloo problem, whereas for t ≥ 3 very little is known.
In this paper, we show, among other things, that the above necessary conditions are sufficient whenever 2w + 1 ≥ (t + 1)N, α_i > 1 for every i ∈ {1, 2, ..., t}, and gcd (N_1, N_2, ..., N_t) > 1. We also provide sufficient conditions for the solvability of the generalized Oberwolfach problem over an arbitrary graph and, in particular, the complete equipartite graph
The first families of highly symmetric Kirkman Triple Systems whose orders fill a congruence class
No full textKirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet, in comparison with Steiner triple systems, little is known about their automorphism groups. In particular, there is no known congruence class representing the orders of a KTS with a number of automorphisms at least close to the number of points. We partially fill this gap by proving that whenever v≡ 39 (mod 72), or v≡ 4 e48 + 3 (mod 4 e96) and e≥ 0 , there exists a KTS on v points having at least v- 3 automorphisms. This is only one of the consequences of an investigation on the KTSs with an automorphism group G acting sharply transitively on all but three points. Our methods are all constructive and yield KTSs which in many cases inherit some of the automorphisms of G, thus increasing the total number of symmetries. To obtain these results it was necessary to introduce new types of difference families (the doubly disjoint ones) and difference matrices (the splittable ones) which we believe are interesting by themselves
Graph products and new solutions to Oberwolfach problems
No full textA method to construct simple graphs starting from known ones is introduced. This method can be applied in many different situations and when applied to regular graphs and to their decompositions, a new regular graph is obtained together with a new decomposition. Using this tecnique infinitely many new solutions to the Oberolfach problem, in both the classic and equipartite case are constructed
On 2-pyramidal Hamiltonian cycle systems
No full textA Hamiltonian cycle system of the complete graph on 2v vertices minus a 1 factor (briefly, an HCS(2v)) is 2-pyramidal if it admits an automorphism group of order 2v - 2 fixing two vertices. In spite of the fact that the very first example of an HCS(2v) is very old and 2-pyramidal, a thorough investigation of this class of HCSs is lacking. We give first evidence that there is a strong relationship between 2-pyramidal HCS(2v) and 1-rotational Hamiltonian cycle systems of the complete graph on 2v-1 vertices. Then, as main result, we determine the full automorphism group of every 2-pyramidal HCS(2v). This allows us to obtain an exponential lower bound on the number of non-isomorphic 2-pyramidal HCS (2v)
- …
