## Cores and shells of graphs.(English)Zbl 1274.05399

In this paper author studies some structural aspects of graphs. The $$k$$-core $$C_k(G)$$ of a graph $$G$$ is the maximal induced subgraph $$H\subset 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 $$v$$ is the largest value of $$k$$ such that $$v\in C_k(G)$$, and the maximum core number $$\widehat {C}(G)$$ of a graph $$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$$.
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 proved. Some applications of cores and shells to graph coloring and domination are considered, some structural properties of $$2$$-cores are shown and some applications of monocore graphs into structure and eigenvalues of graphs are discussed.

### MSC:

 05C75 Structural characterization of families of graphs 05C15 Coloring of graphs and hypergraphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: