Transversals of Longest Paths
classification
💻 cs.DM
math.CO
keywords
graphconnectedlongestomegapathswhenbipartitecardinality
read the original abstract
Let $\lpt(G)$ be the minimum cardinality of a set of vertices that intersects all longest paths in a graph $G$. Let $\omega(G)$ be the size of a maximum clique in $G$, and $\tw(G)$ be the treewidth of $G$. We prove that $ \lpt(G) \leq \max\{1,\omega(G)-2\}$ when $G$ is a connected chordal graph; that $\lpt(G) =1$ when $G$ is a connected bipartite permutation graph or a connected full substar graph; and that $\lpt(G) \leq \tw(G)$ for any connected graph $G$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.