Maximum and minimum degree in iterated line graphs

Abstract

In this thesis we analyze two papers, both by Dr. Stephen G. Hartke and Dr. Aparna W. Higginson, on maximum and minimum degrees of a graph $G$ under iterated line graph operations. Let $\Delta_{k}$ and $\delta_{k}$ denote the minimum and the maximum degrees, respectively, of the $k^{th}$ iterated line graph $L^{k}(G)$. It is shown that if $G$ is not a path, then, there exist integers $A$ and $B$ such that for all $k>A$, $\Delta_{k+1}=2\Delta_{k}-2$ and for all $k>B$, $\delta_{k+1}=2\delta_{k}-2$.