Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$k$-core; $k$-shell; monocore; coloring; domination
$k$-core; $k$-shell; monocore; coloring; domination
Summary:
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.
References:
[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 10.1186/1471-2105-4-2
[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 10.7151/dmgt.1637 | MR 2993514
[6] Bickle, A.: The $k$-Cores of a Graph. Ph.D. Dissertation, Western Michigan University (2010). MR 2827272
[7] Bickle, A., Phillips, B.: $t$-Tone colorings of graphs. Submitted.
[8] Bollobas, B.: Extremal Graph Theory. Academic Press (1978). MR 0506522 | Zbl 0419.05031
[9] Caro, Y., Roditty, Y.: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20 (1985), 167-180. MR 0824858 | Zbl 0623.05031
[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 10.1155/S016117129000031X | MR 1038667
[11] Chartrand, G., Lesniak, L.: Graphs and Digraphs (4th ed.). Chapman & Hall, Bocca Raton, FL (2005). MR 2107429 | Zbl 1057.05001
[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall, Bocca Raton, FL (2009). MR 2450569 | Zbl 1169.05001
[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 10.1016/S0012-365X(02)00569-1 | MR 1955714 | Zbl 1014.05023
[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 10.1112/jlms/s1-27.1.85 | MR 0045371 | Zbl 0046.41001
[15] Dirac, G. A.: Homomorphism theorems for graphs. Math Ann. 153 (1964), 69-80. DOI 10.1007/BF01361708 | MR 0160203
[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 0593902
[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 1605684 | Zbl 0890.05002
[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 2532884
[20] Lick, D. R., White, A. T.: $k$-degenerate graphs. Canad. J. Math. 22 (1970), 1082-1096. DOI 10.4153/CJM-1970-125-1 | MR 0266812 | Zbl 0202.23502
[21] Łuczak, T.: Size and connectivity of the $k$-core of a random graph. Discrete Math. 91 (1991), 61-68. DOI 10.1016/0012-365X(91)90162-U | MR 1120887 | Zbl 0752.05046
[22] McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749-762. DOI 10.1002/jgt.3190130610 | MR 1025896 | Zbl 0708.05058
[23] Ore, O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, RI (1962). MR 0150753 | Zbl 0105.35401
[24] Reed, B.: Paths, stars, and the number three. Combin. Probab. Comput. 5 (1996), 277-295. DOI 10.1017/S0963548300002042 | MR 1411088 | Zbl 0857.05052
[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 10.1016/0378-8733(83)90028-X | MR 0721295
[27] Sohn, M. Y., Xudong, Y.: Domination in graphs of minimum degree four. J. Korean Math. Soc. 46 (2009), 759-773. DOI 10.4134/JKMS.2009.46.4.759 | MR 2532884
[28] Szekeras, G., Wilf, H. S.: An inequality for the chromatic number of a graph. J. Comb. Th. 4 (1968), 1-3. DOI 10.1016/S0021-9800(68)80081-X | MR 0218269
[29] West, D.: Introduction to Graph Theory, (2nd ed.). Prentice Hall of India, New Delhi (2001). MR 1367739
[30] Wilf, H. S.: The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42 (1967), 330-332. DOI 10.1112/jlms/s1-42.1.330 | MR 0207593 | Zbl 0144.45202
[31] Wuchty, S., Almaas, E.: Peeling the yeast protein network. Proteomics 5 (2005), 444-449. DOI 10.1002/pmic.200400962
[32] Xing, H., Sun, L., Chen, X.: Domination in graphs of minimum degree five. Graph. Combinator. 22 (2006), 127-143. DOI 10.1007/s00373-006-0638-3 | MR 2221014 | Zbl 1091.05054
Search
Partner of
