\mychapter{Introduction}
\setcounter{page}{1}

%Split Semisimple Groups
%Representations
%Cohomology
%Cohomological Invariants
%Tits Algebras


%Historically, there have been many results concerning sufficient conditions for implying certain sets of cycles in graphs.  My thesis aims to extend many of these well known results to similar results on sets of {\it chorded} (and sometimes even {\it doubly chorded}) cycles.  In particular, we consider the minimum degree, $\delta(G)$ and a Ore-type degree sum condition, $\sigma_2(G)$ of a graph $G$, sufficient to guarantee the existence of $k$ vertex disjoint chorded cycles, often containing specified elements of the graph, such as certain vertices or edges.  Further, we extend a result on vertex disjoint cycles and chorded cycles to an analogous result on vertex disjoint cycles and {\it doubly} chorded cycles. We define a new graph property called chorded pancyclicity, and investigate a density condition and forbidden subgraphs in claw-free graphs that imply this new property. Specifically, we forbid certain paths and triangles with pe?In this chapter we aim to establish the notation and state the main facts to be used throughout this dissertation. 
\section{History}

In the field of extremal graph theory, we are interested in the way that local graph properties can affect global properties of the graph.  We often investigate how far we can push certain properties of a graph before we can guarantee the existence of some other property, or even some specific structure in the graph.  In the past, there have been many results concerning sufficient conditions for graphs containing certain types of cycles, such as hamiltonian cycles, or certain sets of cycles. In particular, there has been a large focus on sets of vertex disjoint cycles that contain specified graph elements including certain sets of vertices, or sets of independent edges, for example.   Arguably one of the most famous such results is due to Corr\'adi and Hajnal \cite{Corradi}.

\begin{theorem}{\rm\cite{Corradi}} Let $G$ be a graph of order $n\ge3k$ for an integer $k\ge 1$ and suppose the minimum degree of $G$, $\delta(G)\ge 2k$.  Then $G$ contains a set of $k$ vertex disjoint cycles. 
\label{thm:corradihajnal} 
\end{theorem}

Enomoto proved a stronger result in \cite{E} for the Ore-type degree sum condition, $\sigma_2(G)$ as follows.

\begin{theorem} {\rm\cite{E}} Suppose $G$ is a graph of order $n\ge 3k$ for an integer $k\ge 1$.  If $\sigma_2(G)\ge 4k-1$, then $G$ contains a set of $k$ vertex disjoint cycles.  
\label{thm:enomoto}
\end{theorem}

 A type of cycle that was largely ignored until relatively recently is a chorded cycle, that is a cycle with an edge between two vertices that are nonadjacent on the cycle.  In this thesis, we turn our attention to chorded cycles and we extend many well-known results on cycles or vertex disjoint sets of cycles to analogous results on chorded cycles and sometimes even doubly chorded cycles.  Admittedly, we were not the first to focus on chorded cycles.  Back in 1960, Posa \cite{Lovasz} asked the question: which graph properties imply the existence of a cycle with a chord?  The first answer was due to Czipzer (see Problem 10.2 in \cite{Lovasz}) in 1963; he found that any graph with minimum degree at least three must contain a chorded cycle. However, it was not until 45 years later in 2008, that the interest in chorded cycles began to pick up steam.  That year, Finkel \cite{F} extended the Corr\'adi-Hajnal theorem to a chorded cycle version.
 
 \begin{theorem}{\rm\cite{F}}  Let $G$ be a graph of order $n\ge 4k$ for an integer $k\ge1$ and suppose the minimum degree of $G$, $\delta(G)\ge 3k$.  Then $G$ contains a set of $k$ vertex disjoint chorded cycles.
 \label{thm:finkel}  
 \end{theorem}

Further, this result is sharp as can be easily seen from the complete bipartite graph $K_{3k-1, n-3k+1}$. (Note that the smallest chorded cycle in a complete bipartite graph is a $6$-cycle.)  In 2005, Faudree and Gould \cite{jillfg} found the best lower bound for the order of neighborhood unions of nonadjacent vertices that implies the existence of $k$ disjoint cycles in a graph.  This result was extended to chorded cycles in 2012 by Gould, Hirohata, and Horn \cite{GHH} and independently Gao, Li, and Yan \cite{GLY}.  They proved the following result. 

\begin{theorem}{\rm\cite{GHH}}, {\rm\cite{GLY}}  For an integer $k\ge1$, le $G$ be a graph of order $n\ge 4k$ such that for any pair of nonadjacent vertices $x$ and $y$, $|N(x)\cup N(y)|\ge 4k+1$.  Then $G$ contains at least $k$ vertex disjoint chorded cycles.  
\end{theorem}

Inspired by these extensions of theorems on sets of cycles to theorems on sets of chorded cycles, we consider other cycle results to extend similarly. These results are stated in $\S2.2$.
\vspace{.1in}

\section{Some Basics (Definitions and Notation)} In this thesis, we assume a working knowledge of graph theory. For a thorough background on the subject, see \cite{G}.   We consider only finite simple graphs, that is, graphs with no loops or multiple edges.  Let $G=(V(G), E(G))$ be a finite simple graph.  We denote the {\it degree} of a vertex $v\in V(G)$ as $deg_G(v)$ which is the number of edges incident to $v$ in $G$.  For a set of vertices $\{u_1, u_2, \ldots, u_k\}$ and a subgraph $H$ of $G$, let $\deg_H(u_1, u_2, \ldots, u_k)$ be the sum of the degrees of the vertices $u_i$ (for $1\le i\le k$) to the subgraph $H$.  The set of vertices adjacent to $v$ in the graph $G$ is called the {\it neighborhood} of $v$ in $G$ and is denoted $N_G(v)$. The {\it minimum degree} of a graph is the smallest degree over all the vertices in $G$ and is denoted $\delta(G)$. Similarly, the {\it maximum degree} of $G$ is denoted $\Delta(G)$.  The {\it independence number},  $\alpha(G)$ of a graph is the largest number of vertices in a mutually nonadjacent set of vertices in $G$.  For a noncompete graph $G$, we define the following Ore-type degree sum condition $$\sigma_2(G)=\min\{\deg_G(x)+\deg_G(y)| xy\not\in E(G)\}.$$ If $G$ is a complete graph, then by convention $\sigma_2(G):=\infty$.  

Let $G$ be a graph and $P_t$ be a path on $t$ vertices. A path $P$ is denoted $P=\langle u_1, u_2,\ldots, u_m \rangle$ for $u_1, u_2, \ldots, u_m\in V(G)$. Next we define two terms crucial to this thesis on chorded cycles.

\begin{definition} Given a cycle $C$, an edge $e=v_1v_2$ is called a {\bf chord} of $C$ if its endpoints, $v_1$ and $v_2$, are not adjacent on $C$.  We then say that $C$ is a {\bf chorded cycle}.
\end{definition}

Further, a \emph{doubly chorded cycle} is a cycle with at least two chords.  Next we define two important concepts for the study of forbidden subgraphs, which we will investigate in Chapter $4$.

\begin{definition}
A vertex-induced subgraph, which we will simply refer to as an {\bf induced subgraph}, is a subset of the vertices of a graph $G$ together with any edges whose endpoints are both in the subset of $V(G)$. For a subset $S \subseteq V(G)$, we denote the subgraph of $G$ induced by the vertices of $S$ as $G[S]$. 
\end{definition}

\begin{definition} 
Given a subgraph $H$ of a graph $G$, we say $G$ is {\bf $H$-free} if $G$ does not contain a subgraph isomorphic to $H$. 
\end{definition}

In Chapter $4$, we consider only $K_{1, 3}$-free (or {\it claw}-free) graphs, and we will forbid certain paths and triangles with pendant paths.  Let $Z_i$ be a triangle with a pendant $P_{i}$ adjacent to one of the vertices of the triangle.  In particular, we will focus on the graphs $Z_1$ and $Z_2$, shown below (Figure 1a).
\begin{center}
{\scalebox{.7}{ \includegraphics{z1andz2.jpg} }}\\
{\bf Figure 1a.}
\end{center}
We will also use the following terms in Chapter $4$.

\begin{definition} A graph $G$ is called  {\bf traceable} if it contains a path consisting of every vertex in $V(G)$.
\end{definition}

\begin{definition} The {\bf diameter} of a graph $G$, denoted $d(G)$, is the longest shortest path between any two vertices in $V(G)$.
\end{definition}

For any terms not defined here, see \cite{G}.

%define bipartite?
%add claw and z_1 notation?

\vspace{.1in}



\section{Known Results for Sets of Cycles Containing Specified Graph Elements}  In Chapter $2$, we consider minimum degree conditions $\delta(G)$ and degree sum conditions $\sigma_2(G)$.  Our goal is to find sufficient such conditions to imply the existence of vertex disjoint sets of chorded cycles, often containing specific graph elements.  In particular, we extend some well-known results for sets of cycles much like Gould, Hirohata, and Horn's \cite{GHH} extension of Gould's previous result with Faudree on neighborhood unions in \cite{jillfg}.  In 2000, Egawa, Faudree, Gyori, Ishigami, Schelp, and Wang \cite{EFG} proved the following result for vertex disjoint cycles.

\begin{theorem}{\rm\cite{EFG}} Let $G$ be a graph on $n\ge 4k$ vertices for an integer $k\ge1$ and let $\{e_1, e_2, \ldots, e_k\}$ be a set of $k$ independent edges in $G$.  If the minimum degree $$\displaystyle\delta(G)\ge\frac{n+2k-2}{2},$$ then $G$ contains $k$ vertex disjoint cycles $\{C_1, C_2, \ldots, C_k\}$ such that $e_i\in E(C_i)$ and $3\le |V(C_i)|\le 4$ for all $1\le i\le k$. 
\end{theorem}

This result can be extended in multiple ways, as shown in Chapter $2$.  Next, we note a similar known result about placing specified vertices on cycles.

\begin{theorem}{\rm\cite{EEF}} For an integer $k\ge1$, let $G$ be a graph of order $n\ge 6k-3$.  If the minimum degree $$\delta(G)\ge\frac{n}{2},$$ then for any set of $k$ vertices $\{v_1, v_2, \ldots, v_k\}$ in $G$, there exists a set of $k$ vertex disjoint cycles $\{C_1, C_2, \ldots, C_k\}$ such that $v_i\in V(C_i)$ and $3\le|V(C_i)|\le 5$ for all $1\le i\le k$.   
\end{theorem}

%\begin{theorem} {\rm \cite{EEF}}
%Let $G$ be a graph of order $n\ge 6k-3$ for some integer $k\ge1$.  If $$\delta(G)\ge \frac{n}{2},$$ then for any set of $k$ vertices $\{v_1, v_2, \ldots, v_k\}$ there exists a set of $k$ vertex disjoint cycles $\{C_1, C_2, \ldots, C_k\}$ such that $v_i\in V(C_i)$ and $|V(C_i)|\le 5$ for all $1\le i\le k$. 
%\end{theorem}

In Chapter $2$, we extend this result to chorded cycles.  Further, we consider the basic question of when a set of $k$ independent edges can be chords for $k$ vertex disjoint cycles, one per cycle. We also investigate when the $k$ vertex disjoint chorded cycles can be extended to span the entire vertex set of a graph.  
\vspace{.1in}
 

\section{Known Results for Vertex Disjoint Cycles and Chorded Cycles} The motivation for the results in Chapter $3$ comes from a natural conjecture based on Theorems \ref{thm:corradihajnal} and \ref{thm:enomoto} proposed by Bialostocki, Finkel, and Gy\'arf\'as, in \cite{BFG}.


\begin{conjecture}{\rm\cite{BFG}} Let $r, s\ge 0$ be two integers and let $G$ with a graph of order $n\ge 3r+4s$ and minimum degree $\delta(G)\ge 2r+3s$.  Then $G$ contains a collection of $r+s$ vertex disjoint cycles such that $s$ of them are chorded cycles.  
\end{conjecture} 

This minimum degree bound is sharp \cite{GLY}.  The $r=0, s=2$ case and the $s=1$ cases were shown to be true in \cite{BFG}.  The $r=0$ case was completed by Finkel \cite{F} in the aforementioned Theorem \ref{thm:finkel}. 

The general conjecture was proved to be true by Babu and Diwan \cite{Badu}, and Chiba and Fujita \cite{Chiba} independently. In particular, the authors in \cite{Badu, Chiba} generalized the minimum degree condition to a degree sum condition, and proved the following theorem.

\begin{theorem} [\cite{Badu, Chiba}] 
Let $r \ge 0$, $s \ge 0$ be two integers and $G$ be a graph with $|V(G)| \ge 3r+4s$ and $\sigma_2(G) \ge 4r+6s-1$, then $G$ contains $r+s$ vertex disjoint cycles such that $s$ of them are chorded cycles.
\label{thm:ccc}
\end{theorem}

Balister, Li and Schelp \cite{Balister} improved on Theorem \ref{thm:ccc} under a minimum degree condition.

\begin{theorem}[\cite{Balister}] \label{DDCThmb}
If $G$ is a simple graph on $|V(G)| \ge 3r+4s$ vertices with $\delta(G) \ge 2r+3s$, then $G$ contains $r+s$ vertex disjoint cycles, each of $s$ of them with two chords, or a $C_4$ with one chord.
\end{theorem}

Qiao and Zhang \cite{Qiao} proved that $|V(G)| \ge 4k$ and $\delta(G) \ge \lceil 7k/2 \rceil $ can ensure $k$ vertex disjoint doubly chorded cycles in any graph $G$. Gould, Hirohata and Horn \cite{GHH} improved the degree condition in \cite{Qiao} to a degree sum condition and proved the following result.

\begin{theorem} [\cite{GHH}] \label{DDCThmc}
If $G$ is a graph with $|V(G)| \ge 6k$ and $\sigma_2(G) \ge 6k-1$, then $G$ contains $k$ vertex disjoint doubly chorded cycles.
\end{theorem}

Motivated by the above theorems, in Chapter $3$ our goal is to guarantee a collection of $r+s$ vertex disjoint cycles, such that $s$ of them are doubly chorded cycles.

\vspace{.1in}


\section{Known Results for Pancyclic Graphs}  Forbidden subgraphs for hamiltonian properties in graphs have been widely studied (for an overview, see \cite{FG}).  A property even stronger than hamiltonicity is pancyclicity in a graph $G$, which is the property of containing a cycle of every possible length $i=3, 4, \ldots, |V(G)|$.  Pancyclicity only arises in 2-connected graphs and is one of the well-studied cycle properties in graphs.  In Chapter $4$, we extend this property and study the notion of {\it chorded pancyclicity}, that is, containing a chorded cycle of every possible length $i=4, 5, \ldots, |V(G)|$.  We study the density necessary to guarantee this property in a graph.  There are also many known forbidden subgraph results for pancyclicity.  We take the natural step of extending some of these results from pancyclicity to chorded pancyclicity.   

In Chapter $4$, we extend the following theorem to a similar result on chorded pancyclicity, with slight variations in some conditions.

 \begin{theorem} Let $R, S$ be connected graphs and let $G$ ($G\neq C_n$) be a 2-connected graph of order $n\ge10$.  Then if $G$ is $\{R,S\}$-free then $G$ is pancyclic for $R=K_{1,3}$ and $S$ is either $P_4, P_5, P_6, Z_1,$ or $Z_2$.  
\label{thm:pan}
 \end{theorem}


The proof of a theorem in \cite{GH} yields the following result.

\begin{theorem}{\rm\cite{GH}}
If $G$ is a 2-connected graph of order $n\ge 10$ that contains no induced subgraph isomorphic to $K_{1,3}$ or $Z_1$, then $G$ is either a cycle or $G$ is pancyclic.  
\label{thm:z1}
\end{theorem}


Gould and Jacobson proved a similar result for $Z_2$ in \cite{GJ}.  

\begin{theorem}{\rm\cite{GJ}}
If $G$ is a 2-connected graph of order $n\ge 10$ that contains no induced subgraph isomorphic to $K_{1,3}$ or $Z_2$, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:z2} 
\end{theorem}

Faudree, Ryjacek, and Schiermeyer proved a similar result for certain paths in \cite{FRS}. 


\begin{theorem} {\rm\cite{FRS}}
If $G$ is a 2-connected graph of order $n\ge 6$ that is $\{K_{1,3}, P_5\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p5i} 
\end{theorem}

\begin{theorem} {\rm\cite{FRS}}
If $G$ is a 2-connected graph of order $n\ge 10$ that is $\{K_{1,3}, P_6\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p6} 
\end{theorem}

Theorem \ref{thm:p5i} implies the following result for $P_4$.   

\begin{theorem}
If $G$ is a 2-connected graph of order $n\ge 6$ that is $\{K_{1,3}, P_4\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p4} 
\end{theorem}


In Chapter $4$ of this thesis, we extend each of these results to similar results on chorded pancyclicity.   




