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.


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: Link