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.