TRANSVERSALS OF LONGEST PATHS AND CYCLES

被引：19

作者：

Rautenbach, Dieter ^{[1
]}

Sereni, Jean-Sebastien ^{[2
]}

机构：

[1] Univ Ulm, Inst Optimierung & Operat Res, D-89069 Ulm, Germany

[2] LORIA, CNRS, F-54506 Vandoeuvre Les Nancy, France

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2014年 / 28卷 / 01期

关键词：

longest path; longest cycle; transversal; GRAPHS;

D O I：

10.1137/130910658

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：335 / 341

页数：7