Opuscula Math. 33, no. 4 (2013), 631-640
http://dx.doi.org/10.7494/OpMath.2013.33.4.631

Opuscula Mathematica

# On the longest path in a recursively partitionable graph

Julien Bensmail

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 $$\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.

Keywords: recursively partitionable graph, longest path.

Mathematics Subject Classification: 05C99, 68R10.

Full text (pdf)

• Julien Bensmail
• Univ. Bordeaux LaBRI, UMR 5800, F-33400 Talence, France
• CNRS, LaBRI, UMR 5800, F-33400 Talence, France
• Revised: 2013-05-23.
• Accepted: 2013-05-24. 