We make progress toward a characterization of the graphs $H$ such that every connected $H$-free graph has a longest path transversal of size $1$. In particular, we show that the graphs $H$ on at most $4$ vertices satisfying this property are exactly the linear forests. We also show that if the order of a connected graph $G$ is large relative to its connectivity $\kappa(G)$, and its independence number $\alpha(G)$ satisfies $\alpha(G) \le \kappa(G) + 2$, then each vertex of maximum degree forms a longest path transversal of size $1$.
翻译:我们逐步对图表进行定性,使每个连接的无H美元图表都有最长的横切路径,大小为$1美元。特别是,我们显示,最多能满足这一属性的4美元顶脊的图表完全就是线性森林。我们还显示,如果连接的图表的顺序与其连通性相当大,1美元等于kapa(G)美元,而其独立号为$\alpha(G)美元能够满足$\alpha(G)\le\kappa(G)+2美元,那么,每个最大度的顶端将形成最长的大小为$的横切路径。