Estimating the number of graphs containing very long induced paths.
Steven K. Butler · 2008
Let P(n, k) denote the number of graphs on n + k vertices that contain Pn, a path on n vertices, as an induced subgraph. In this note we will find upper and lower bounds for P(n, k). Using these bounds we show that for k fixed, P(n, k) behaves roughly like an exponential function of n as n gets large. 1