On the longest path in a recursively partitionable graph

Abstract

A connected graph $G$ with order $n \geq 1$ is said to be recursively arbitrarily partitionable (R-AP for short) if either it is isomorphic to $K_1$, or for every sequence $(n_1, \ldots , n_p)$ of positive integers summing up to n there exists a partition $(V_1, \ldots , V_p)$ of $V(G)$ such that each $V_i$ induces a connected R-AP subgraph of $G$ on $n_i$ vertices. Since previous investigations, it is believed that a R-AP graph should be »almost traceable« somehow. We first show that the longest path of a R-AP graph on $n$ vertices is not constantly lower than $n$ for every $n$. This is done by exhibiting a graph family $C$ such that, for every positive constant $c \geq 1$, there is a R-AP graph in $C$ that has arbitrary order $n$ and whose longest path has order $n-c$. We then investigate the largest positive constant $c' \lt 1$ such that every R-AP graph on n vertices has its longest path passing through $n \cdot c'$ vertices. In particular, we show that $c' \leq \frac{2}{3}.$ This result holds for R-AP graphs with arbitrary connectivity.