A Star-Comb Lemma for Finite Digraphs
Abstract
It is well-known that for every set $U$ of vertices in a connected graph $G$ there is either a subdivided star in $G$ with a large number of leaves in $U$, or a comb in $G$ with a large number of teeth in $U$.In this paper we extend this property to directed graphs. More precisely, we prove that for every $n \in \mathbb{N}$ and every sufficiently large set $U$ of vertices in a strongly connected directed graph $D$, there exists a strongly connected butterfly minor of $D$ with $n$ teeth in $U$ that is either 'shaped' by a star or 'shaped' by a comb.
Fields of Study & Subjects
Coding theory and cryptography
graph theory and CDMA systems
Advanced Graph Theory Research
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 3
- Publication date
- 7 August 2026
- Language
- EN