Estimating the Number of Graphs Containing Very Long Induced Paths

Abstract

Let $\mathcal{P}(n,k)$ denote the number of graphs on $n+k$ vertices that contain $P_n$, a path on $n$ vertices, as an induced subgraph. In this note, we will find upper and lower bounds for $\mathcal{P}(n,k)$. Using these bounds, we show that for $k$ fixed, $\mathcal{P}(n,k)$ behaves roughly like an exponential function of $n$ as $n$ gets large.