论文标题
在弦图中相交的最长路径
Intersecting longest paths in chordal graphs
论文作者
论文摘要
我们考虑与和弦图中最长路径相交所需的最小顶点的大小。这样的集合被称为最长路径横向。我们表明，如果$ω（g）$是和弦图$ g $的集团数量，那么最多有$ 4 \ lceil \ frac {ω（g）} {5} {5} \ rceil $的订单横向。我们还考虑了最长周期的类似问题，并表明，如果$ g $是2个连接的和弦图，那么横向与最长的顺序相交，最多是$ 2 \ lceil \ lceil \ frac {ω（ω（g）} {3} {3} {3} {3} \ rceil $。
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if $ω(G)$ is the clique number of a chordal graph $G$, then there is a transversal of order at most $4\lceil\frac{ω(G)}{5}\rceil$. We also consider the analogous question for longest cycles, and show that if $G$ is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most $2\lceil\frac{ω(G)}{3}\rceil$.
