A note on barely transitive groups

We study some properties for barely transitive group.     

A note on infinite transitive graphs

In [4] Jung and Watkins proved that for a connected infinite graph X either κ_∞(X) = ∞ holds or X is a strip, if Aut(X) contains a transitive abelian subgroup G. Here we prove the same result under weaker assumptions.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.     

On transitive decompositions of disconnected graphs

We investigate transitive decompositions of disconnected graphs, and show that these behave very differently from a related class of algebraic graph decompositions, known as homogeneous factorisations. We conclude that although the study of homogeneous factorisations admits a natural reduction to those cases where the graph is connected, the study of transitive decompositions does not.     

Monochromatic sinks in nearly transitive arc-colored tournaments

Let T be the set of all arc-colored tournaments, with any number of colors, that contain no rainbow 3-cycles, i.e., no 3-cycles whose three arcs are colored with three distinct colors. We prove that if T∈T and if each strong component of T is a single vertex or isomorphic to an upset tournament, then T contains a monochromatic sink. We also prove that if T∈T and T contains a vertex x such that T−x is transitive, then T contains a monochromatic sink. The latter result is best possible in the sense that, for each n≥5, there exists an n-tournament T such that (T−x)−y is transitive for some two distinct vertices x and y in T, and T can be arc-colored with five colors such that T∈T, but T contains no monochromatic sink.     

A note on Hamiltonian decompositions of Cayley graphs

We define a class Γ of 4-regular Cayley graphs on abelian groups and prove every element of Γ to be decomposable into two Hamiltonian cycles. This result is a special case of a conjecture ofB. Alspach and includes a theorem ofJ.-C. Bermond et al. as a subcase.     

A note on transitive permutation groups of prime degree

LetG be a nonsolvable transitive permutation group of prime degreep. LetP be a Sylow-p-subgroup ofG and letq be a generator of the subgroup ofN _G(P) fixing one point. Assume that |N _G(P)|=p(p?1) and that there exists an elementj inG such thatj ^?1qj=q^(p+1)/2. We shall prove that a group that satisfies the above condition must be the symmetric group onp points, andp is of the form 4n+1.     

Examples of rank 3 product action transitive decompositions

A transitive decomposition is a pair where Γ is a graph and is a partition of the arc set of Γ such that there is a subgroup of automorphisms of Γ which leaves invariant and transitively permutes the parts in . In an earlier paper we gave a characterisation of G-transitive decompositions where Γ is the graph product K _m × K _m and G is a rank 3 group of product action type. This characterisation showed that every such decomposition arose from a 2-transitive decomposition of K _m via one of two general constructions. Here we use results of Sibley to give an explicit classification of those which arise from 2-transitive edge-decompositions of K _m .      

A note about topologically transitive cylindrical cascades

Letσ: Σ → Σ be a topologically mixing shift of finite type. Letβ: Σ → ? be a continuous function, and σ _β be the skew-product ofσ byβ. Assume that σ _β has a positive semi-orbit that reaches any upper height, and any lower height. Then, arbitrarilyC ⁰-close toβ there exists a Hölder mapβ′: Σ → ? such that the skew-product $\sigma _{\beta ^\prime } $ ofσ byβ′ is topologically transitive.     

A note on path and cycle decompositions of graphs

In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph G has a smallest path (resp. path-cycle) decomposition P such that every odd vertex of G is the endpoint of exactly one path of P? This note gives a negative answer to both questions.     

A note on finite groups in which c-permutability is transitive

A subgroup H of G is c-permutable in G if there exists a permutable subgroup P of?G such that HP=G and H∩P≦H _pG , where H _pG is the largest permutable subgroup of?G contained in?H. A?group G is called CPT-group if c-permutability is transitive in?G. A?number of new characterizations of finite solvable CPT-groups are given.     

A note on transitive orientations with maximum sets of sources and sinks

Given a transitive orientation of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in , respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation . A pair of subsets S,TV(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation , respectively. We describe algorithms for finding a transitive orientation with a maximum source–sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity.     

Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments

A long-standing conjecture of Kelly states that every regular tournament on n$n$ vertices can be decomposed into (n−1)/2$(n-1)/2$ edge-disjoint Hamilton cycles. We prove this conjecture for large n$n$. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G$G$ on n$n$ vertices whose degree is linear in n$n$ and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erd?s on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.     

A well-quasi-order for tournaments

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order; that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general; but we show it is true for tournaments (a tournament is a directed complete graph).     

A note on conservative galaxies,Skolem systems,cyclic cycle decompositions,and Heffter arrays

The conservative number of a graph $G$ is the minimum positive integer $M$, such that $G$ admits an orientation and a labeling of its edges by distinct integers in $\{1,2,\dots ,M\}$, such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if $M=\left|E\left(G\right)\right|$. It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size $M$ is $M$ for $M\equiv 0$, $3(mod4)$, and $M+1$ otherwise. Consequently, given positive integers $m_1$, $m_2$, …, $m_n$ with $m_i\ge 3$ for $1\le i\le n$, we construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of the complete graph $K_{2M+1}$, where $M={\sum }_{i=1}^n{m}_i$. Also, we prove necessary and sufficient conditions for the existence of a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of $K_{2M+2}?F$, where $F$ is a 1-factor. Furthermore, we give a sufficient condition for a subset of ${\mathbb{Z}}_v?\left\{0\right\}$ to be sequenceable.     

A note about a theorem by maamoun on decompositions of digraphs into elementary directed paths or cycles

Maamoun (J. Combin. Theory Ser. B38 (1985), 97–101) has found an upper bound on the minimum number of elementary directed paths or elementary directed cycles which can partition the arcs of a digraph G. We slightly improve his theorem by specifying the number of elementary directed paths needed in such a partition.     

Multipartite tournaments: A survey

A multipartite or c-partite tournament is an orientation of a complete c-partite graph. In this survey we mainly describe results on directed cycles and paths in strongly connected c-partite tournaments for c?3. In addition, we include about 40 open problems and conjectures.