# Tag Info

10

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+2}$ as induced subgraph, where the $P_{r+2}$ is the path on $r+2$ vertices. The equivalence can be seen as follows. The two degree-one vertices in the \$P_{r+2}...

5

Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018). In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we ...

2

Yes. By Proposition 2.3 of [1], all elementary fractional extreme points of the LP correspond to subgraphs that contain odd cycles, and therefore if the graph contains no odd cycles, the LP has an optimal solution that takes on only integer values. [1] G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. ...

Only top voted, non community-wiki answers of a minimum length are eligible