We examine bicoset digraphs and their natural properties from the point of view of symmetry. We then consider connected bicoset digraphs that are X-joins with collections of empty graphs, and show that their automorphism groups can be obtained from their natural irreducible quotients. We further show that such digraphs can be recognised from their connection sets.

A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers $s,t \ge 1$ there exists a finite number $F(s,t)$ such that the vertex set of every digraph of minimum out-degree at least $F(s,t)$ can be partitioned into non-empty parts $A$ and $B$ such that the subdigraphs induced on $A$ and $B$ have minimum out-degree at least $s$ and $t$, respectively.

In this short note, we prove that if $F(2,2)$ exists, then all the numbers $F(s,t)$ with $s,t\ge 1$ exist and satisfy $F(s,t)=\Theta (s+t)$. In consequence, the problem of Alon and Stiebitz reduces to the case $s=t=2$. Moreover, the numbers $F(s,t)$ with $s,t \ge 2$ either all exist and grow linearly, or all of them do not exist.

We show that for every $\eta \gt 0$ every sufficiently large $n$-vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta )\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs.

Further, we show that in the same setting, $D$ contains every $k$-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$.

Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$.

Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.

Let $\tau$ be a partition of the positive integer $n$. A partition of the set $\{1,2,\dots,n\}$ is said to be of type $\tau$ if the sizes of its classes form the partition $\tau$ of $n$. It is known that the semigroup $S(\tau)$, generated by all the transformations with kernels of type $\tau$, is idempotent generated. When $\tau$ has a unique non-singleton class of size $d$, the difficult Middle Levels Conjecture of combinatorics obstructs the application of known techniques for determining the rank and idempotent rank of $S(\tau)$. We further develop existing techniques, associating with a subset $U$ of the set of all idempotents of $S(\tau)$ with kernels of type $\tau$ a directed graph $D(U)$; the directed graph $D(U)$ is strongly connected if and only if $U$ is a generating set for $S(\tau)$, a result which leads to a proof if the fact that the rank and the idempotent rank of $S(\tau)$ are both equal to

$$ \max\biggl\{\binom{n}{d},\binom{n}{d+1}\biggr\}. $$

AMS 2000 Mathematics subject classification: Primary 20M20; 05A18; 05A17; 05C20