#### Abstract

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!).

#### Degree

MS

#### College and Department

Physical and Mathematical Sciences; Mathematics

#### Rights

http://lib.byu.edu/about/copyright/

#### BYU ScholarsArchive Citation

Butler, Steven Kay, "Bounding the Number of Graphs Containing Very Long Induced Paths" (2003). *All Theses and Dissertations*. 31.

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

#### Date Submitted

2003-02-07

#### Document Type

Thesis

#### Handle

http://hdl.lib.byu.edu/1877/etd158

#### Keywords

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