Covering 2‐colored complete digraphs by monochromatic d $d$‐dominating digraphs
Covering 2‐colored complete digraphs by monochromatic d $d$‐dominating digraphs
复制标题
用单色 d $d$– 主导有向图覆盖 2—彩色完整有向图
DOI：
10.1002/jgt.22804
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Gyárfás, András
中科院分区：
文献类型：
--
作者：
DeBiasio, Louis;Gyárfás, András
如果每组至多 d $d$ 个顶点都有一个共同的外邻居，则有向图是 d $d$ 支配的。对于所有整数 d ≥ 2 $d\ge 2$，设 f ( d ) $f(d)$ 为最小整数，使得每个 2 边彩色（有限或无限）完整有向图（包括环）的顶点最多可以被 f ( d ) $f(d)$ 单色 d $d$ 支配子图的顶点覆盖。请注意，f ( d ) $f(d)$ 的存在性并不明显——事实上，激发本文的问题只是为了确定 f ( d ) $f(d)$ 是否有界，即使对于 d = 2 $d=2$ 也是如此。我们对所有 d ≥ 2 $d\ge 2$ 都肯定地回答这个问题，证明 4 ≤ f ( 2 ) ≤ 8 $4\le f(2)\le 8$ 和 2 d ≤ f ( d ) ≤ 2 d d d − 1 d − 1 对于所有 d ≥ 3 $2d\le f(d)\le 2d\left(\frac{{d}^{d}-1}{d-1}\right)\,\,\text{对于所有}\,\,d\ge 3$。我们还举了一个例子来说明两种以上的颜色不存在类似的界限。我们的结果为有关 d $d$ 简并图的 Ramsey 数的 Burr-Erdős 猜想的无限类比的问题提供了肯定的答案。此外，我们的结果的一个特例与 d $d$‐ 自相矛盾的锦标赛的属性有关。
A digraph is d $d$‐dominatingif every set of at most d $d$ vertices has a common out‐neighbor. For all integers d ≥ 2 $d\ge 2$, let f ( d ) $f(d)$ be the smallest integer such that the vertices of every 2‐edge‐colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most f ( d ) $f(d)$ monochromatic d $d$‐dominating subgraphs. Note that the existence of f ( d ) $f(d)$ is not obvious – indeed, the question which motivated this paper was simply to determine whether f ( d ) $f(d)$ is bounded, even for d = 2 $d=2$. We answer this question affirmatively for all d ≥ 2 $d\ge 2$, proving 4 ≤ f ( 2 ) ≤ 8 $4\le f(2)\le 8$ and 2 d ≤ f ( d ) ≤ 2 d d d − 1 d − 1 for all d ≥ 3 $2d\le f(d)\le 2d\left(\frac{{d}^{d}-1}{d-1}\right)\,\,\text{for all}\,\,d\ge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr‐Erdős conjecture on the Ramsey numbers of d $d$‐degenerate graphs. Moreover, a special case of our result is related to properties of d $d$‐paradoxical tournaments.