ترغب بنشر مسار تعليمي؟ اضغط هنا

A Method to Construct $1$-Rotational Factorizations of Complete Graphs and Solutions to the Oberwolfach Problem

52   0   0.0 ( 0 )
 نشر من قبل Daniel McGinnis
 تاريخ النشر 2018
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

The concept of a $1$-rotational factorization of a complete graph under a finite group $G$ was studied in detail by Buratti and Rinaldi. They found that if $G$ admits a $1$-rotational $2$-factorization, then the involutions of $G$ are pairwise conjugate. We extend their result by showing that if a finite group $G$ admits a $1$-rotational $k=2^nm$-factorization where $ngeq 1$, and $m$ is odd, then $G$ has at most $m(2^n-1)$ conjugacy classes containing involutions. Also, we show that if $G$ has exactly $m(2^n-1)$ 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 $2n$-factorization under $G times mathbb{Z}_n$ given a $1$-rotational $2$-factorization under a finite group $G$. This construction, given a $1$-rotational solution to the Oberwolfach problem $OP(a_{infty},a_1, a_2 cdots, a_n)$, allows us to find a solution to $OP(2a_{infty}-1,^2a_1, ^2a_2cdots, ^2a_n)$ when the $a_i$s are even ($i eq infty$), and $OP(p(a_{infty}-1)+1, ^pa_1, ^pa_2 cdots, ^pa_n)$ when $p$ is an odd prime, with no restrictions on the $a_i$s.



قيم البحث

اقرأ أيضاً

We prove that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result gives a new solution to the Oberwolfach problem.
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$-factor. We show that this can be achieved for all large $n$. We actually prove a significantly more general result, whic h allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large $n$.
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, denoted poly_H(G), is the largest number of color s in an H-polychromatic coloring. In this paper, poly_H(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition poly_H(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.
Let $textbf{k} := (k_1,ldots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;textbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ con tain no clique of order $k_c$. Write $F(n;textbf{k})$ to denote the maximum of $F(G;textbf{k})$ over all graphs $G$ on $n$ vertices. There are currently very few known exact (or asymptotic) results known for this problem, posed by ErdH{o}s and Rothschild in 1974. We prove some new exact results for $n to infty$: (i) A sufficient condition on $textbf{k}$ which guarantees that every extremal graph is a complete multipartite graph, which systematically recovers all existing exact results. (ii) Addressing the original question of ErdH{o}s and Rothschild, in the case $textbf{k}=(3,ldots,3)$ of length $7$, the unique extremal graph is the complete balanced $8$-partite graph, with colourings coming from Hadamard matrices of order $8$. (iii) In the case $textbf{k}=(k+1,k)$, for which the sufficient condition in (i) does not hold, for $3 leq k leq 10$, the unique extremal graph is complete $k$-partite with one part of size less than $k$ and the other parts as equal in size as possible.
A universal cycle for permutations of length $n$ is a cyclic word or permutation, any factor of which is order-isomorphic to exactly one permutation of length $n$, and containing all permutations of length $n$ as factors. It is well known that univer sal cycles for permutations of length $n$ exist. However, all known ways to construct such cycles are rather complicated. For example, in the original paper establishing the existence of the universal cycles, constructing such a cycle involves finding an Eulerian cycle in a certain graph and then dealing with partially ordered sets. In this paper, we offer a simple way to generate a universal cycle for permutations of length $n$, which is based on applying a greedy algorithm to a permutation of length $n-1$. We prove that this approach gives a unique universal cycle $Pi_n$ for permutations, and we study properties of $Pi_n$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا