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...

Let $G(\circ )$ and $G(*)$ be two groups of finite order $n$, and suppose that they share a normal subgroup $S$ such that $u\circ v=u*v$ if $u\in S$ or $v\in S$. Cases when $G/S$ is cyclic or dihedral and when $u\circ v\ne u*v$ for exactly $n^2/4$ pairs $(u,v)\in G\times G$ have been shown to be of crucial importance when studying pairs of 2-groups with the latter property. In such cases one can describe two general constructions how to get all possible $G(*)$ from a given $G=G(\circ )$. The constructions, denoted by $G[\alpha ,h]$ and $G[\beta ,\gamma ,h]$, respectively, depend on a coset $\alpha$ (or two cosets $\beta$ and $\gamma$) modulo $S$, and on an...

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...