\documentclass{article}
\usepackage[utf8]{inputenc}
%\usepackage[czech]{babel}
\usepackage{graphicx}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumerate}
\usepackage{epstopdf}

\newtheorem*{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{algorithm}[theorem]{Algorithm}

%\newcommand{deg}{\texttt{deg}}

\title{Construction of Graphs with a Fixed Peeling Number}
\author{
James Abello${}^1$
\footnote{\tt\small abello@dimacs.rutgers.edu}
\and
Karel Tesař${}^2$
\footnote{\tt\small tesar@kam.mff.cuni.cz}
}

\begin{document}
\maketitle

\begin{center}
${}^1$Rutgers University in Piscataway, NY, DIMACS Center for Discrete Mathematics and Theorethical Computer Science, USA.

\vspace{0.5cm}
${}^2$Charles University in Prague, Faculty of Mathematics and Physics, Czech Republic.
\end{center}

\vspace{1cm}
\begin{abstract}
A peeling number of vertices in a graph are numbers defined by the following process. We repeatedly remove a vertex $v$
with a minimum degree and define a peeling number of $v$ as a maximum degree which we have already removed. Peeling
numbers are important for example in social networks. Peeling number tells us "how important vertex is". We focus on
graphs where all vertices have the same peeling number. We show how construct these graphs and show that a class
of edge extremal graphs equals to generalized trees.
\end{abstract}

\newpage
\section{Introduction}
We say that a graph $G$ is $k$-degenerate if every $H \subseteq G$ has a vertex with degree at most $k$. Specifically we
may remove vertices one by one in order such that every removed vertex has degree at most $k$ at the time of removing.
This order of vertices we call a $k$-degenerate-order.

Now we generalize this order such that we always remove a vertex $v$ with a minimum degree in a graph $G$. Let $d$ be
the maximum degree which we have already removed. Then after removing a vertex $v$ we define a peeling number of $v$
as $d$. It is easy to see that peeling numbers are uniquely determined. We define a peeling-order as an order of vertices with
nondecreasing peeling numbers.

We may define a peeling numbers in another way. We have a several of phasions of vertex removing. In a phase $i$ we
remove vertices with a degree $i$ or less. Vertex removed during a phase $i$ has a peeling number $i$.
Let us see that both process give us the same peeling numbers.

In the next section we will be interested in graphs where all of their vertices have the same peeling number.

\begin{definition}
Let us denote as $FP_k$ 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}

\begin{observation}
Class $FP_k$ contains exactly graphs which are $k$-degenerate and have a minimum degree equals to $k$.
\end{observation}

In Section 2, we show a construction of graphs in $FP_2$, next we define extremal cases of $FP_k$ graphs and find
a construction of those graphs. Finally we show that every graph $G \in FP_k$ is a subgraph of some extremal graph
from $FP_k$. Afterwards in Section 3, we show a generalization of trees and show that a class of extremal $FP_k$ graphs
equals this class.
In Section 4, we show one result for $k$-degeneracy graphs. Specifically we show that one can find an independent set $I$ in
$k$-degenerate graph $G$ such that the graph $G \setminus I$ is at most $(k-1)$-degenerate.

\section{Constructions of $FP_k$ graphs}
We would like to find some operations such that we may construct every graph from $FP_k$ using these operations on some set
of initial graphs and such that $FP_k$ is closed under these operations. These initial graphs are called primitive graphs
with a respect to $FP_k$ and given operations. First, we find operations for the class $FP_2$ where primitive graphs are
isomorphic to disjoint union of triangles and we prove the following theorem.

\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 neighbour $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 neighbour.
\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 \quad\&\quad \deg(w)=3$.
\end{enumerate}
\end{theorem}

\begin{proof}
We know that there exists a vertex $v$ with a degree two in every component. We proceed by a case analysis according to
the neighbors $u_1$, $u_2$ of $v$ where we assume that $\deg(u_1) \leq \deg(u_2)$.
\begin{itemize}
\item Both neighbors have degree greater than two. Then we may erase a vertex $v$. According to $2$-degeneracy there still
exists another vertex with degree two and according to $FP_2$ there is no vertex with degree less than two.

\item $\deg(u_1)=2$ and $u_2$ is not neighbour of $u_1$. Then we may contract an edge $vu_1$. The new vertex has
degree two.

\item $\deg(u_1)=2 \quad\&\quad \deg(u_2)>3$ and $u_2$ is a neighbour of  $u_1$. Then we erase vertices $v$ and $u_1$
and we still stay in $FP_2$ because of $2$-degeneracy.

\item $\deg(u_1)=2 \quad\&\quad \deg(u_2)=3$ and $u_2$ is a neighbour of  $u_1$. If another neighbour of $u_2$ has degree
two, we may contract an edge between it and $u_2$. In the other case we may erase a triangle $vu_1u_2$.

\item  $\deg(u_1)=2 \quad\&\quad \deg(u_2)=2$ and $u_2$ is a neighbour of  $u_1$. So this component is a triangle.
\end{itemize}
\end{proof}

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

\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}

Now we define extremal graphs in $FP_k$. We use them later for construction of the class $FP_k$ for other values of $k$.
We say that $G \in FP_k$ on $n$ vertices is extremal if it has the maximal number of edges. Here is the formal definition.

\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}

First we notice that every $FP_k$ extremal graph on $n$ vertices has the same number of edges.

\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}

\begin{proof}
We know that $G$ is $k$-degenerate and it has a minimum degree $k$. So every vertex $v_i$ in
$k$-degenerate-order
has $\min\{k, i\}$ forward edges where $i$ is a backward position in that order. If this was not true then we could add
a new edge and stay into a $FP_k$ class.

Now it follows that the number of edges is exactly ${k \choose 2} + k(n-k)$.
\end{proof}

From this fact and $k$-degenerate-order follows the construction of extremal $FP_k$ graphs.

\begin{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{claim}

\begin{figure}
  \centering
  \includegraphics[scale=1.5]{img/extremal.eps}
  \caption{Example of an extremal graph from $FP_3$. First we have a clique $K_3$, by adding one vertex we get a clique $K_4$
  and then we add vertices $v_5, v_6, v_7, v_8$.}
  \label{fig:extremal}
\end{figure}

Next we prove that any $G$ from $FP_k$ is a subgraph of some extremal graph from $FP_k$ on the same number of vertices.
To prove this, we look at $k$-degenerate-order of $G$ and expand it into $k$-degenerate-order of some extremal graph.

\begin{theorem}
Let $G$ be an graph from $FP_k$ on $n$ vertices. Then there exists an extremal graph $H \in FP_k$ such that $H$ also has
$n$ vertices and $G$ is a subgraph of $H$.
\end{theorem}

\begin{proof}
We take a $k$-degenerate-order of $G$ -- every vertex $v_i \in G$ has at most $\min\{k, i\}$ forward edges. Additionally
we construct an extremal graph $H$ and add to every vertex all forward edges which are also in $G$. The rest of the edges can
be added arbitrarily.
\end{proof}

From the last theorem we get a construction of any graph $G \in FP_k$. First we construct an arbitrary extremal $H$ such
that $G \subseteq H$ and then we remove some edges. Let us note that the earlier construction for $FP_2$
is more convenient for proofs by induction, because we are only adding new vertices and edges and we never delete anything. 
On the other hand if we want to obtain a result only for extremal graphs from $FP_k$, then the last construction is also usable.

\section{Generalization of trees}
In trees every leaf has degree one and the leafs form an independent set and if we remove all of them we obtain another tree.
Repeating this process, we end with $K_1$ or $K_2$. Now we try to generalize this idea. For a given graph $G$ and the positive
integer $k$ we apply the following peeling process.

\begin{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{algorithm}

This algorithm may output various graphs. We focus on cases where we end up with a clique $K_k$ or $K_{k+1}$.

\begin{figure}
  \centering
  \includegraphics[scale=1.3]{img/tree3.eps}
  \caption{Example of a tree from $\mathcal{T}_3$.}
  \label{fig:tree3}
\end{figure}

\begin{definition}
Let $k$ be a natural number 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}$.

We say that a vertex of $G \in \mathcal{T}_k$ with degree $k$ which is not in the final clique $K_k$ or $K_{k+1}$ is a leaf.
\end{definition}

The interesting thing, about this class of graphs, is that the class of generalized trees is equivalent to extremal $FP_k$ graphs.

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

\begin{proof}
If we take some $G \in \mathcal{T}_k$ then we may repeatively remove some indepentent sets $I_1, \ldots, I_l$ of vertices of
degree $k$ and end with $K_k$ or $K_{k+1}$. If we remove the vertices one by one we actually get a construction of extremal
case of $FP_k$. So $G$ is also in $EFP_k$

For a given graph $G \in EFP_k$ we prove by induction on $|V(G)|$ that $G$ is also contained in $\mathcal{T}_k$. The cliques $K_k$ and $K_{k+1}$ trivially are in $\mathcal{T}_k$. Let us assume that $G$ is a graph with at least $k+2$ vertices. We have
a $k$-degenerate order of $G$ where every
vertex except the last $k$ has $k$ forward edges. Therefore every vertex with degree $k$ has only forward edges. So they
form an independent set $I$ if we remove this independent set we get $G \setminus I$ which is also from $EFP_k$ and smaller.
So $G \setminus I$ is from $\mathcal{T}_k$ and if we add $I$ into this graph as a leafs we get that $G$ is also
from $\mathcal{T}_k$. 
\end{proof}

Here follows another interesting thing about $\mathcal{T}_k$.

\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}

\begin{proof}
We prove it by induction. For a clique $K_{k+1}$ on vertices $\{1, 2, \ldots, k+1\}$, for every $1 \leq i \leq k$ we define $T_i$ as
a graph on vertices $\{1, 2, \ldots, k+1\}$ with edges $\{\{i, j\}:\quad j \geq i\}$. Obviously these trees are edge disjoint and
every edge is covered.

If we have a larger graph $G$, then we remove some leaf $l \in V(G)$. By induction on $|V(G)|$ we have trees
$T_1, \ldots, T_k$ which
are edge disjoint and their union is $G \setminus \{l\}$. Now we add a vertex $l$ in all of them such that every $T_i$ stays to be
connected. We may do this because there are at most $i-1$ vertices which are not in $T_i$. So first we choose a neighbor of $l$
which is in $T_k$, then we choose a neighbor which is in $T_{k-1}$ and so on until the last one which remains is in $T_1$.
Obviously every $T_i$ is still a tree and $T_i$ and $T_j$ are edge disjoint for every $i$ and $j$. We also covered
every edge incident with $l$.
\end{proof}

\section{$k$-degeneracy 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}

\begin{proof}
We take a $k$-degenerate order and greedily find a proper coloring of a graph $G$ with colors $\{1, 2, \ldots, k+1\}$.
We take vertices one by one from the last one to the first one. Everyone of them has at most $k$ forward edges
so there exists a color which we may use. We always use the smallest possible color.

Now we claim that a set of vertices with color $1$ is the independent set we are looking for. Every vertex $v$ either have color $1$
or some of it's forward neighbour have color one. So if a vertex $v$ remains, then its forward degree decrease at least by one and hence
the degeneracy of $G \setminus \{v: v \textrm{ has color } 1\}$ is at most $(k-1)$-degenerate.
\end{proof}

\section{Acknowledgements}
This article was created as a project on a Research Experiences for Undergraduates (REU) 2013 program.

\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{document}