Cores and shells of graphs. (English) Zbl 1274.05399

Bickle, Allan

Math. Bohem. 138, No. 1, 43-59 (2013).

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.

Reviewer: Přemysl Holub (Plzeň)

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.)

Keywords:

structural aspects of graphs; \(k\)-core; maximal induced subgraph; \(k\)-shell; monocore; coloring; domination; core number; monocore graphs