Transversals of Longest Paths and Cycles
Transversals of Longest Paths and Cycles
复制标题
DOI：
10.1137/130910658
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
D. Rautenbach;Jean-Sébastien Sereni
中科院分区：
文献类型：
--
作者：
D. Rautenbach;Jean-Sébastien Sereni
Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.
Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.