论文标题
覆盖稀疏图的周期
Covering cycles in sparse graphs
论文作者
论文摘要
令$ k \ geq 2 $为整数。 Kouider和Lonc证明了每个图$ g $的顶点集，其中$ n \ geq n_0（k）$ vertices和最低度至少$ n/k $可以由$ k -1 $ cycles覆盖。我们的主要结果指出，每$α> 0 $和$ p = p = p（n）\ in（0，1] $，对于图形$ g $，具有最低度$ $ $ $（1/k +α）np $稀疏的图形$ g $的结论相同。 e_g（x，y）\ leq p | x || y | + o（np \ sqrt {| x || y |}/\ log^3 n）\ qquad \ forall x，y \ subseteq v（g）。 \]特别是，这使我们能够确定随机和伪图的局部弹性，相对于通过固定数量的循环的顶点覆盖率而言。证明在稀疏扩展器图中使用吸收方法的版本。
Let $k \geq 2$ be an integer. Kouider and Lonc proved that the vertex set of every graph $G$ with $n \geq n_0(k)$ vertices and minimum degree at least $n/k$ can be covered by $k - 1$ cycles. Our main result states that for every $α> 0$ and $p = p(n) \in (0, 1]$, the same conclusion holds for graphs $G$ with minimum degree $(1/k + α)np$ that are sparse in the sense that \[ e_G(X,Y) \leq p|X||Y| + o(np\sqrt{|X||Y|}/\log^3 n) \qquad \forall X,Y\subseteq V(G). \] In particular, this allows us to determine the local resilience of random and pseudorandom graphs with respect to having a vertex cover by a fixed number of cycles. The proof uses a version of the absorbing method in sparse expander graphs.
