Geodesic
Cores and shells of graphs
Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 43-59

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2013.143229
Classification : 05C15, 05C69, 05C75
Keywords: $k$-core; $k$-shell; monocore; coloring; domination 
Bickle, Allan. Cores and shells of graphs. Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 43-59. doi: 10.21136/MB.2013.143229
@article{10_21136_MB_2013_143229,
     author = {Bickle, Allan},
     title = {Cores and shells of graphs},
     journal = {Mathematica Bohemica},
     pages = {43--59},
     year = {2013},
     volume = {138},
     number = {1},
     doi = {10.21136/MB.2013.143229},
     mrnumber = {3076220},
     zbl = {1274.05399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143229/}
}
TY  - JOUR
AU  - Bickle, Allan
TI  - Cores and shells of graphs
JO  - Mathematica Bohemica
PY  - 2013
SP  - 43
EP  - 59
VL  - 138
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143229/
DO  - 10.21136/MB.2013.143229
LA  - en
ID  - 10_21136_MB_2013_143229
ER  - 
%0 Journal Article
%A Bickle, Allan
%T Cores and shells of graphs
%J Mathematica Bohemica
%D 2013
%P 43-59
%V 138
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143229/
%R 10.21136/MB.2013.143229
%G en
%F 10_21136_MB_2013_143229

[1] M. Altaf-Ul-Amin, K. Nishikata, T. Koma, T. Miyasato, Y. Shinbo, M. Arifuzzaman, C. Wada, M. Maeda, et al.: Prediction of protein functions based on $k$-cores of protein-protein interaction networks and amino acid sequences. Genome Informatics 14 (2003), 498-499.

[2] Alvarez-Hamelin, J., Dall'Asta, L., Barrat, A., Vespignani, A.: $k$-core decomposition: a tool for the visualization of large scale networks. Advances in Neural Information Processing Systems 18 (2006), 41.

[3] Bader, G., Hogue, C.: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4 (2003). | DOI

[4] Batagelj, V., Zaversnik, M.: An $O(m)$ algorithm for cores decomposition of networks. Unpublished manuscript: http://vlado.fmf.uni-lj.si/pub/networks/doc/cores/cores.pdf (2003).

[5] Bickle, A.: Structural results on maximal $k$-degenerate graphs. Discuss. Math., Graph Theory 32 (2012), 659-676. | DOI | MR

[6] Bickle, A.: The $k$-Cores of a Graph. Ph.D. Dissertation, Western Michigan University (2010). | MR

[7] Bickle, A., Phillips, B.: $t$-Tone colorings of graphs. Submitted.

[8] Bollobas, B.: Extremal Graph Theory. Academic Press (1978). | MR | Zbl

[9] Caro, Y., Roditty, Y.: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20 (1985), 167-180. | MR | Zbl

[10] Caro, Y., Roditty, Y.: A note on the $k$-domination number of a graph. Internat. J. Math. Math. Sci. 13 (1990), 205-206. | DOI | MR

[11] Chartrand, G., Lesniak, L.: Graphs and Digraphs (4th ed.). Chapman & Hall, Bocca Raton, FL (2005). | MR | Zbl

[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall, Bocca Raton, FL (2009). | MR | Zbl

[13] Coffman, W. C., Hakimi, S. L., Schmeichel, E.: Bounds for the chromatic number of graphs with partial information. Discrete Math. 263 (2003), 47-59. | DOI | MR | Zbl

[14] Dirac, G. A.: A property of 4-chromatic graphs and some remarks on critical graphs. J. Lond. Math. Soc. 27 (1952), 85-92. | DOI | MR | Zbl

[15] Dirac, G. A.: Homomorphism theorems for graphs. Math Ann. 153 (1964), 69-80. | DOI | MR

[16] Erdős, P., Rubin, A., Taylor, H.: Choosability in graphs. Combinatorics, Graph Theory and Computing, Proc. West Coast Conf., Arcata/Calif., 1979 Utilitas Mathematica Publishing, Winnipeg (1980), 125-157. | MR

[17] Gaertler, M., Patrignani, M.: Dynamic analysis of the autonomous system graph. Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (2004), 13-24.

[18] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR | Zbl

[19] Jianxiang, C., Minyong, S., Sohn, M. Young, Xudong, Y.: Domination in graphs of minimum degree six. J. Appl. Math. & Informatics 26 (2008), 1085-1100. | MR

[20] Lick, D. R., White, A. T.: $k$-degenerate graphs. Canad. J. Math. 22 (1970), 1082-1096. | DOI | MR | Zbl

[21] Łuczak, T.: Size and connectivity of the $k$-core of a random graph. Discrete Math. 91 (1991), 61-68. | DOI | MR | Zbl

[22] McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749-762. | DOI | MR | Zbl

[23] Ore, O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, RI (1962). | MR | Zbl

[24] Reed, B.: Paths, stars, and the number three. Combin. Probab. Comput. 5 (1996), 277-295. | DOI | MR | Zbl

[25] Schwenk, A. J., Wilson, R. J.: Eigenvalues of graphs. Selected Topics in Graph Theory L. W. Beineke, R. J. Wilson Academic Press, London (1978), 307-336.

[26] Seidman, S. B.: Network structure and minimum degree. Social Networks 5 (1983), 269-287. | DOI | MR

[27] Sohn, M. Y., Xudong, Y.: Domination in graphs of minimum degree four. J. Korean Math. Soc. 46 (2009), 759-773. | DOI | MR

[28] Szekeras, G., Wilf, H. S.: An inequality for the chromatic number of a graph. J. Comb. Th. 4 (1968), 1-3. | DOI | MR

[29] West, D.: Introduction to Graph Theory, (2nd ed.). Prentice Hall of India, New Delhi (2001). | MR

[30] Wilf, H. S.: The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42 (1967), 330-332. | DOI | MR | Zbl

[31] Wuchty, S., Almaas, E.: Peeling the yeast protein network. Proteomics 5 (2005), 444-449. | DOI

[32] Xing, H., Sun, L., Chen, X.: Domination in graphs of minimum degree five. Graph. Combinator. 22 (2006), 127-143. | DOI | MR | Zbl

Cité par Sources :