Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths.
In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya counting we will then be able to get upper and lower bounds for graphs containing a long path as an induced subgraph.
In particular, if we let P(n,k) be the number of graphs on n+k vertices which contains P_n, a path on n vertices, as an induced subgraph then using our upper and lower bounds for P(n,k) we will show that for any fixed value of k that P(n,k)~2^(nk+k_C_2)/(2k!).
College and Department
Physical and Mathematical Sciences; Mathematics
BYU ScholarsArchive Citation
Butler, Steven Kay, "Bounding the Number of Graphs Containing Very Long Induced Paths" (2003). All Theses and Dissertations. 31.
mathematics, combinatorics, graph theory, paths, induced paths, asymptotic behavior, stirling numbers, polya counting, Burnsides theorem