论文标题
司额最长路径横向
Sublinear Longest Path Transversals
论文作者
论文摘要
我们表明，连接的图允许均值最长的路径横向。这改善了Rautenbach和Sereni的较早结果，并且与五十岁的问题有关，即连接的图是否允许最长的恒定路径横向。相同的技术使我们能够证明$ 2 $连接的图形允许均值最长的循环横向。
We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that $2$-connected graphs admit sublinear longest cycle transversals.
