Cores and shells of graphs
Allan Bickle · Mathematica Bohemica · 2013
The $k$-core of a graph $G$, $C_{k}(G)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta (G)\geq k$, if it exists. For $k>0$, the $k$-shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$-core and not contained in the $(k+1)$-core. The core number of a vertex is the largest value for $k$ such that $v\in C_{k}(G)$, and the maximum core number of a graph, $\widehat {C}(G)$, is the maximum of the core numbers of the vertices of $G$. A graph $G$ is $k$-monocore if $\widehat {C}(G)=\delta (G)=k$. \endgraf This paper discusses some basic results on the structure of $k$-cores and $k$-shells. In particular, an operation characterization of 2-monocore graphs is proven. Some applications of cores and shells to graph coloring and domination are considered.