Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Bounding The Number Of Graphs Containing Very Long Induced Paths, Steven Kay Butler
Bounding The Number Of Graphs Containing Very Long Induced Paths, Steven Kay Butler
Theses and Dissertations
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 …