Bounding the Number of Graphs Containing Very Long Induced Paths

Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths. <p>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. <p>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!).

Name thesis:degree_name

MS

Grantor dc:publisher

Brigham Young University - Provo

Author dc:creator

• Butler, Steven Kay

• mathematics
• combinatorics
• graph theory
• paths
• induced paths
• asymptotic behavior
• stirling numbers
• polya counting
• Burnsides theorem

Language dc:language

English

Repository record dc:identifier

https://scholarsarchive.byu.edu/etd/31

OAI identifier oai:identifier

oai:scholarsarchive.byu.edu:etd-1030