TY  - JOUR
ID  - Bensmail2013
LB  - Bensmail2013
AU  - Bensmail, Julien
TI  - On the longest path in a recursively partitionable graph
ST  - On the longest path in a recursively partitionable graph
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2013
VL  - 33
IS  - 4
SP  - 631
EP  - 640
DO  - http://dx.doi.org/10.7494/OpMath.2013.33.4.631
UR  - http://dx.doi.org/10.7494/OpMath.2013.33.4.631
AB  - 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 \(\mathcal{C}\) such that, for every positive constant \(c \geq 1\), there is a R-AP graph in \(\mathcal{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.
KW  - recursively partitionable graph
KW  - longest path
SN  - 1232-9274
ER  -