| Title:
|
Cores and shells of graphs (English) |
| Author:
|
Bickle, Allan |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
138 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
43-59 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$k$-core |
| Keyword:
|
$k$-shell |
| Keyword:
|
monocore |
| Keyword:
|
coloring |
| Keyword:
|
domination |
| MSC:
|
05C15 |
| MSC:
|
05C69 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 1274.05399 |
| idMR:
|
MR3076220 |
| DOI:
|
10.21136/MB.2013.143229 |
| . |
| Date available:
|
2013-03-02T18:52:01Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143229 |
| . |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[3] Bader, G., Hogue, C.: An automated method for finding molecular complexes in large protein interaction networks.BMC Bioinformatics 4 (2003). 10.1186/1471-2105-4-2 |
| Reference:
|
[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). |
| Reference:
|
[5] Bickle, A.: Structural results on maximal $k$-degenerate graphs.Discuss. Math., Graph Theory 32 (2012), 659-676. MR 2993514, 10.7151/dmgt.1637 |
| Reference:
|
[6] Bickle, A.: The $k$-Cores of a Graph.Ph.D. Dissertation, Western Michigan University (2010). MR 2827272 |
| Reference:
|
[7] Bickle, A., Phillips, B.: $t$-Tone colorings of graphs.Submitted. |
| Reference:
|
[8] Bollobas, B.: Extremal Graph Theory.Academic Press (1978). Zbl 0419.05031, MR 0506522 |
| Reference:
|
[9] Caro, Y., Roditty, Y.: On the vertex-independence number and star decomposition of graphs.Ars Combin. 20 (1985), 167-180. Zbl 0623.05031, MR 0824858 |
| Reference:
|
[10] Caro, Y., Roditty, Y.: A note on the $k$-domination number of a graph. Internat.J. Math. Math. Sci. 13 (1990), 205-206. MR 1038667, 10.1155/S016117129000031X |
| Reference:
|
[11] Chartrand, G., Lesniak, L.: Graphs and Digraphs (4th ed.).Chapman & Hall, Bocca Raton, FL (2005). Zbl 1057.05001, MR 2107429 |
| Reference:
|
[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory.Chapman & Hall, Bocca Raton, FL (2009). Zbl 1169.05001, MR 2450569 |
| Reference:
|
[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. Zbl 1014.05023, MR 1955714, 10.1016/S0012-365X(02)00569-1 |
| Reference:
|
[14] Dirac, G. A.: A property of 4-chromatic graphs and some remarks on critical graphs.J. Lond. Math. Soc. 27 (1952), 85-92. Zbl 0046.41001, MR 0045371, 10.1112/jlms/s1-27.1.85 |
| Reference:
|
[15] Dirac, G. A.: Homomorphism theorems for graphs.Math Ann. 153 (1964), 69-80. MR 0160203, 10.1007/BF01361708 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[18] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs.Marcel Dekker, New York (1998). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[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 |
| Reference:
|
[20] Lick, D. R., White, A. T.: $k$-degenerate graphs.Canad. J. Math. 22 (1970), 1082-1096. Zbl 0202.23502, MR 0266812, 10.4153/CJM-1970-125-1 |
| Reference:
|
[21] Łuczak, T.: Size and connectivity of the $k$-core of a random graph.Discrete Math. 91 (1991), 61-68. Zbl 0752.05046, MR 1120887, 10.1016/0012-365X(91)90162-U |
| Reference:
|
[22] McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two.J. Graph Theory 13 (1989), 749-762. Zbl 0708.05058, MR 1025896, 10.1002/jgt.3190130610 |
| Reference:
|
[23] Ore, O.: Theory of Graphs.Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, RI (1962). Zbl 0105.35401, MR 0150753 |
| Reference:
|
[24] Reed, B.: Paths, stars, and the number three.Combin. Probab. Comput. 5 (1996), 277-295. Zbl 0857.05052, MR 1411088, 10.1017/S0963548300002042 |
| Reference:
|
[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. |
| Reference:
|
[26] Seidman, S. B.: Network structure and minimum degree.Social Networks 5 (1983), 269-287. MR 0721295, 10.1016/0378-8733(83)90028-X |
| Reference:
|
[27] Sohn, M. Y., Xudong, Y.: Domination in graphs of minimum degree four.J. Korean Math. Soc. 46 (2009), 759-773. MR 2532884, 10.4134/JKMS.2009.46.4.759 |
| Reference:
|
[28] Szekeras, G., Wilf, H. S.: An inequality for the chromatic number of a graph.J. Comb. Th. 4 (1968), 1-3. MR 0218269, 10.1016/S0021-9800(68)80081-X |
| Reference:
|
[29] West, D.: Introduction to Graph Theory, (2nd ed.).Prentice Hall of India, New Delhi (2001). MR 1367739 |
| Reference:
|
[30] Wilf, H. S.: The eigenvalues of a graph and its chromatic number.J. Lond. Math. Soc. 42 (1967), 330-332. Zbl 0144.45202, MR 0207593, 10.1112/jlms/s1-42.1.330 |
| Reference:
|
[31] Wuchty, S., Almaas, E.: Peeling the yeast protein network.Proteomics 5 (2005), 444-449. 10.1002/pmic.200400962 |
| Reference:
|
[32] Xing, H., Sun, L., Chen, X.: Domination in graphs of minimum degree five.Graph. Combinator. 22 (2006), 127-143. Zbl 1091.05054, MR 2221014, 10.1007/s00373-006-0638-3 |
| . |
