#### Degree Type

Dissertation

#### Date of Award

2016

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### Major

Mathematics

#### First Advisor

Ryan R. Martin

#### Abstract

The edit distance between two graphs on the same labeled vertex set is defined to be the size of the symmetric difference of the edge sets. The edit distance between a graph, $G$, and a graph property, $\mathcal{H}$, is the minimum edit distance between $G$ and a graph in $\mathcal{H}$. The edit distance function of a graph property $\mathcal{H}$ is a function of $p\in [0,1]$ that measures, in the limit, the maximum normalized edit distance between a graph of density $p$ and $\mathcal{H}$.

In this thesis, we address the edit distance function for the property of having no induced copy of $C_h^t$, the $t^{\mbox{th}}$ power of the cycle of length $h$. For $h\geq 2t(t+1)+1$ and $h$ not divisible by $t+1$, we determine the function for all values of $p$. For $h\geq 2t(t+1)+1$ and $h$ divisible by $t+1$, the function is obtained for all but small values of $p$. We also obtain some results for smaller values of $h$, present alternative proofs of some important previous results using simple optimization techniques and discuss possible extension of the theory to hypergraphs.

#### DOI

https://doi.org/10.31274/etd-180810-5292

#### Copyright Owner

Zhanar Berikkyzy

#### Copyright Date

2016

#### Language

en

#### File Format

application/pdf

#### File Size

53 pages

#### Recommended Citation

Berikkyzy, Zhanar, "The edit distance function: Forbidding induced powers of cycles and other questions" (2016). *Graduate Theses and Dissertations*. 15664.

https://lib.dr.iastate.edu/etd/15664