1,720,987 research outputs found
A constructive solution to the Oberwolfach problem with a large cycle
No full textFor every 2 -regular graph F of order v , the Oberwolfach problem O P(F) asks whether there is a 2 -factorization of Kv (v odd) or Kv minus a 1 -factor (v even) into copies of F. Posed by Ringel in 1967 and extensively studied ever since, this problem is still open. In this paper we construct solutions to O P(F) whenever F contains a cycle of length greater than an explicit lower bound. Our constructions combine the amalgamationdetachment technique with methods aimed at building 2 -factorizations with an automorphism group having a nearly -regular action on the vertex -set. (c) 2024 Elsevier B.V. All rights reserved
Constructing generalized Heffter arrays via near alternating sign matrices
No full textLet S be a subset of a group G (not necessarily abelian) such that S∩−S is empty or contains only elements of order 2, and let h=(h1,...,hm)∈Nm and k=(k1,...,kn)∈Nn. A generalized Heffter array GHASλ(m,n;h,k) over G is an m×n matrix A=(aij) such that: the i-th row (resp. j-th column) of A contains exactly hi (resp. kj) nonzero elements, and the list {aij,−aij|aij≠0} equals λ times the set S∪−S. We speak of a zero sum (resp. nonzero sum) GHA if each row and each column of A sums to zero (resp. a nonzero element), with respect to some ordering. In this paper, we use near alternating sign matrices to build both zero and nonzero sum GHAs, over cyclic groups, having the further strong property of being simple. In particular, we construct zero sum and simple GHAs whose row and column weights are congruent to 0 modulo 4. This result also provides the first infinite family of simple (classic) Heffter arrays to be rectangular (m≠n) and with less than n nonzero entries in each row. Furthermore, we build nonzero sum GHASλ(m,n;h,k) over an arbitrary group G whenever S contains enough noninvolutions, thus extending previous nonconstructive results where ±S=G∖H for some subgroup H of G. Finally, we describe how GHAs can be used to build orthogonal decompositions and biembeddings of Cayley graphs (over groups not necessarily abelian) onto orientable surfaces
Toward a Solution of Archdeacon's Conjecture on Integer Heffter Arrays
No full textIn this article, we make significant progress on a conjecture proposed by Dan Archdeacon on the existence of integer Heffter arrays (Formula presented.) whenever the necessary conditions hold, that is, (Formula presented.), (Formula presented.), (Formula presented.) and (Formula presented.). By constructing integer Heffter array sets, we prove the conjecture in the affirmative whenever (Formula presented.) is odd and (Formula presented.)
A reduction of the spectrum problem for odd sun systems and the prime case
Full text linkA k-cycle with a pendant edge attached to each vertex is called a k-sun. The existence problem for k-sun decompositions of Kv, with k odd, has been solved only when k = 3 or 5. By adapting a method used by Hoffmann, Lindner, and Rodger to reduce the spectrum problem for odd cycle systems of the complete graph, we show that if there is a (Formula presented.) -sun system of (Formula presented.) ((Formula presented.) odd) whenever (Formula presented.) lies in the range (Formula presented.) and satisfies the obvious necessary conditions, then such a system exists for every admissible (Formula presented.). Furthermore, we give a complete solution whenever k is an odd prime
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
Factorizing the Rado graph and infinite complete graphs
Full text linkLet F = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factorization Problem FP(F, Λ) asks whether F can be realized as a factorization of Λ, namely, whether there is a factorization G = {Γα : α ∈ A} of Λ such that each Γα is a copy of Fα. We study this problem when Λ is either the Rado graph R or the complete graph Kא of infinite order א. When F is a countably infinite family, we show that FP(F, R) is solvable if and only if each graph in F has no finite dominating set. We also prove that FP(F, Kא) admits a solution whenever the cardinality of F coincides with the order and the domination numbers of its graphs. For countable complete graphs, we show some non existence results when the domination numbers of the graphs in F are finite. More precisely, we show that there is no factorization of KN into copies of a k-star (that is, the vertex disjoint union of k countable stars) when k = 1, 2, whereas it exists when k ≥ 4, leaving the problem open for k = 3. Finally, we determine sufficient conditions for the graphs of a decomposition to be arranged into resolution classes
- …
