Cores and shells of graphs

Bickle, Allan

Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 43-59.

Résumé

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.

Détail

DOI : 10.21136/MB.2013.143229

Classification : 05C15, 05C69, 05C75
Keywords: $k$-core; $k$-shell; monocore; coloring; domination