Name
Abstract | ||
|---|---|---|
Let G be a graph of order n. Let 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 lct(G) analogously for cycles instead of paths. We prove that lpt(G) <= inverted right perpendicularn/4 - n(2/3)/90inverted left perpendicular if G is connected, and lct(G) <= inverted right perpendicularn/3 - n(2/3)/36inverted left perpendicular if G is 2-connected. Our bound on lct(G) improves an earlier result of Thomassen. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/130910658 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
longest path,longest cycle,transversal | Journal | 28 |
Issue | ISSN | Citations |
1 | 0895-4801 | 3 |
PageRank | References | Authors |
0.51 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dieter Rautenbach | 1 | 946 | 138.87 |
| Jean-Sébastien Sereni | 2 | 269 | 28.69 |