In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdős–Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structureof the largest...

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper, the following question is studied: What is the maximum intersection with γ of a directed cycle of length k? It is proved that for an even k in the range 4 ≤ k ≤ [(n+4)/2], there exists a directed cycle $C_{h\left(k\right)}$ of length h(k), h(k) ∈ k,k-2 with $|A\left(C_{h\left(k\right)}\right)\cap A\left(\gamma \right)|\ge h\left(k\right)-3$ and the result is best possible. In a forthcoming paper the case of directed cycles of length k, k even and k < [(n+4)/2]...

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h\left(k\right)}$ of length h(k), h(k) ∈ k,k-2 with $|A\left(C_{h\left(k\right)}\right)\cap A\left(\gamma \right)|\ge h\left(k\right)-4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was proved.

Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ₄ are best possible.

If $x$ is a vertex of a digraph $D$, then we denote by $d^{+}\left(x\right)$ and $d^{-}\left(x\right)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p\in \mathbb{N}$ such that $d^{+}\left(x\right)=d^{-}\left(x\right)=p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether...

We examine decompositions of complete graphs with an even number of vertices, $K_{2n}$, into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.

Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-{v,w}) = 3, for any two adjacent vertices v and w. For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4. For k = 2 this solves a problem of Nedela and Skoviera [6].

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition ${V_i}_{i=0}^{k-1}$ of V(D) such that every arc in D is a $V_i{V}_{i+1}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths...