\documentclass{beamer}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumerate}
\usepackage{epstopdf}

\usetheme{Warsaw}
\title{Construction of Graphs with a Fixed Peeling Number}
\author{
Karel Tesař,\\
Mentor: James Abello
}
\institute{Research Experiences for Undergraduates}

\begin{document}
% Title page
\begin{frame}
\titlepage
\end{frame}

% Introduction
\section{Introduction}

\begin{frame}
\frametitle{Introduction}

\begin{itemize}
\item<1-> Undirected graph $G = (V,E)$. $V$ are vertices and $E$ are edges.
\item<2-> Degree of a vertex $v \in V$ is a value $\deg(v) = |\{e:\quad v \in v\}|$.
\item<3-> Peeling numbers
\begin{itemize}
\item We repeatedly remove a vertex with a minimum degree. Let $d$ be a maximal degree which we have
already removed.
\item After removing a vertex $v$, we define a peeling number of $v$ as $d$.
\end{itemize}
\item<4->
\begin{definition}
We define $FP_k$ as a class of graphs such that $G \in FP_k$ if and only if every vertex
$v \in G$ has a peeling number $k$.
\end{definition}
\item<5->
Class $FP_k$ contains exactly graphs which are $k$-degenerate and have a minimum degree equals to $k$.
\end{itemize}

\end{frame}

% Construction
\section{Construction}

\begin{frame}
\frametitle{Construction}
\begin{itemize}
\item We want to characterize graphs in the class $FP_k$.
\item We do it constructively.
\item We want to find some operations which are closed in $FP_k$ and by which may help us to construct every
graph from $FP_k$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Construction of $FP_2$}
\begin{theorem}
If $G = (V,E)$ is a graph from $FP_2$ with a component $C$ which is not a triangle, then we can apply
one of the following operations to obtain a graph $G' \in FP_2$ where $|V(G)| > |V(G')|$.
\begin{enumerate}[(a)]
\item Erase a vertex $v \in V$ such that $\deg(v) = 2$ and every neighbor $u$ of $v$ satisfies $\deg(u) > 2$
\item A contraction of an edge $uv \in E$ such that $\deg(u) = \deg(v) = 2$ and $u$ and $v$ have no common neighbor.
\item Erase vertices $u, v \in V$ such that $\deg(u) = deg(v) = 2$ and $u$ and $v$ have a common neighgbour $w$
such that $deg(w) > 3$.
\item Erase a triangle $uvw$ such that $\deg(u) = \deg(v) = 2$ and $\deg(w)=3$.
\end{enumerate}
\end{theorem}
\end{frame}

\begin{frame}
\frametitle{Construction of $FP_2$}
\begin{figure}
  \centering
  \includegraphics[scale=1]{img/operations.eps}
  \caption{Allowed operations for the construction of graphs from $FP_2$. From the left to the right:
  vertex adding, edge subdivision, edge adding and triangle adding.}
  \label{fig:operations}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Construction of $FP_2$}
\begin{corollary}
Every graph $G \in FP_2$ can be constructed from triangles by the following operations
\begin{itemize}
\item adding vertices of degree two,
\item subdivision of edges,
\item adding two vertices of degree two connected by an edge,
\item adding a triangle and connecting it to the rest of the graph by an edge.
\end{itemize}
Note that the class $FP_2$ is closed under these operations.
\end{corollary}

\end{frame}

\begin{frame}
\frametitle{Extremal cases of $FP_k$}
\begin{itemize}
\item It is hard to find a similar construction for $k>2$.
\item First we look only at a construction of an extremal graphs in $FP_k$.
\begin{definition}
We say that a graph $G=(V,E)$ from $FP_k$ on $n$ vertices is \sl{extremal} if for every edge
$e \notin E$ the graph $G + e$ is not in $FP_k$.
\end{definition}
\item It is useful to look at construction of extremal graphs from $FP_k$ because every graph $G \in FP_k$
is a subgraph of some extremal $H \in FP_k$.
\begin{lemma}
Let $G$ be an extremal graph from $FP_k$ on $n$ vertices. Then $G$ has exactly ${k \choose 2} + k(n-k)$ edges.
\end{lemma}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Extremal cases of $FP_k$}
\begin{block}{Claim}
Every extremal graph $G \in FP_k$ on $n>k$ vertices can be constructed from a clique $K_k$ by adding
$(n-k)$ vertices of degree $k$.
\end{block}

\begin{figure}
  \centering
  \includegraphics[scale=1.3]{img/extremal.eps}
  \label{fig:extremal}
\end{figure}
\end{frame}

% Generalization of trees
\section{Generalization of trees}

\begin{frame}
\frametitle{Generalization of trees}
\begin{itemize}
\item<1-> Every leaf in a tree has a degree one.
\item<2-> All leafs form an independent set.
\item<3-> If we remove all leafs we eventualy get another tree.
\item<4-> By repeating this process we get $K_1$ or $K_2$.
\item<5-> Now we try to generalize this idea.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Generalization of trees}
\begin{itemize}
\item For a given graph $G$ and a positive integer $k$ we apply the following peeling process.
\begin{block}{Algorithm}
\it{peel}$(G, k)$:
\begin{enumerate}
\item $I := \{v: \quad \deg(v) = k\}$
\item If $I$ is not independent or there exists a vertex $v$ with degree lower than $k$ then return $G$.
\item $G := G \setminus I$
\item Go to step 1.
\end{enumerate}
\end{block}
\item We focus on cases where we end up with a clique $K_k$ or $K_{k+1}$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Generalization of trees}
\begin{columns}
\column{6cm}
\begin{definition}
Let $k$ be a positive integer and define a class of generalized trees $\mathcal{T}_k$ such that graph $G$ is in $\mathcal{T}_k$
if and only if \it{peel}$(G, k) = K_k$ or \it{peel}$(G, k) = K_{k+1}$.
\end{definition}
\column{6cm}
\begin{figure}
  \centering
  \includegraphics[scale=1]{img/tree3.eps}
  \caption{Example of a tree from $\mathcal{T}_3$.}
\end{figure}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Generalization of trees}
\begin{block}{Claim}
Let $EFP_k$ be a class of extremal graphs from $FP_k$. Then for every $k:\; \mathcal{T}_k = EPF_k$.
\end{block}

\begin{theorem}
For every graph $G$ from $\mathcal{T}_k$ there exist trees $T_1, T_2, \ldots, T_k \in \mathcal{T}_1$ such that $G$
is an edge disjoint union of $T_1, T_2, \ldots, T_k$ and every leaf in $G$ is also a leaf in every tree $T_i$.
\end{theorem}
\end{frame}

\section{$k$-degeneracy and independent sets}

\begin{frame}
\frametitle{$k$-degeneracy and independent sets}
\begin{itemize}
\item Last remark concerns $k$-degenerate graphs and independent sets.
\begin{theorem}
For every $k$-degenerate graph $G=(V,E)$ there exists an independent set $I \subseteq V$ such that $G \setminus I$ is
at most $(k-1)$-degenerate.
\end{theorem}
\end{itemize}
\end{frame}

% References
\section{References}

\begin{frame}
\frametitle{References}
\begin{thebibliography}{99}
\bibitem{abello}
  J. {\sc Abello} and F. {\sc Queyroi}.
  "Fixed Points of Graph Peeling,"
  (2013), Advances in Social Networks.

\bibitem{batagelj}
  V. {\sc Batagelj} and M. {\sc Zaveršnik}.
  "An $\mathcal{O}(m)$ algorithm for cores decomposition of networks,"
  (2003), arXiv:cs/0310049.

\bibitem{lick}
  D. R. {\sc Lick}, and A. T. {\sc White}.
  "$k$-degenerate graphs,"
  Canad. J. Math, vol. 22, pp. 1082–1096, 1970.

\bibitem{montresor}
  A. {\sc Montresor}, F. D. {\sc Pellegrini}, and D. {\sc Miorandi}.
  “Distributed k-core decomposition,”
  CoRR, vol. abs/1103.5320, 2011.

\bibitem{seidman}
  S. {\sc Seidman},
  “Network structure and minimum degree,”
  Social networks, vol. 5, no. 3, pp. 269–287, 1983.

\end{thebibliography}
\end{frame}

\end{document}