Cores and shells of graphs

Allan Bickle

Mathematica Bohemica (2013)

  • Volume: 138, Issue: 1, page 43-59
  • ISSN: 0862-7959

Abstract

top
The k -core of a graph G , C k ( G ) , is the maximal induced subgraph H ⊆ G such that δ ( G ) ≥ 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 ∈ C k ( G ) , and the maximum core number of a graph, C ^ ( G ) , is the maximum of the core numbers of the vertices of G . A graph G is k -monocore if C ^ ( G ) = δ ( 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 proven. Some applications of cores and shells to graph coloring and domination are considered.

How to cite

top

Bickle, Allan. "Cores and shells of graphs." Mathematica Bohemica 138.1 (2013): 43-59. <http://eudml.org/doc/252548>.

@article{Bickle2013,
abstract = {The $k$-core of a graph $G$, $C_\{k\}(G)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta (G)\ge 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$. 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.},
author = {Bickle, Allan},
journal = {Mathematica Bohemica},
keywords = {$k$-core; $k$-shell; monocore; coloring; domination; structural aspects of graphs; -core; maximal induced subgraph; -shell; monocore; coloring; domination; core number; monocore graphs},
language = {eng},
number = {1},
pages = {43-59},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Cores and shells of graphs},
url = {http://eudml.org/doc/252548},
volume = {138},
year = {2013},
}

TY - JOUR
AU - Bickle, Allan
TI - Cores and shells of graphs
JO - Mathematica Bohemica
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 138
IS - 1
SP - 43
EP - 59
AB - The $k$-core of a graph $G$, $C_{k}(G)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta (G)\ge 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$. 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.
LA - eng
KW - $k$-core; $k$-shell; monocore; coloring; domination; structural aspects of graphs; -core; maximal induced subgraph; -shell; monocore; coloring; domination; core number; monocore graphs
UR - http://eudml.org/doc/252548
ER -

References

top
  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. (2003) 
  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. (2006) 
  3. Bader, G., Hogue, C., 10.1186/1471-2105-4-2, BMC Bioinformatics 4 (2003). (2003) DOI10.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). (2003) 
  5. Bickle, A., 10.7151/dmgt.1637, Discuss. Math., Graph Theory 32 (2012), 659-676. (2012) MR2993514DOI10.7151/dmgt.1637
  6. Bickle, A., The k -Cores of a Graph, Ph.D. Dissertation, Western Michigan University (2010). (2010) MR2827272
  7. Bickle, A., Phillips, B., t -Tone colorings of graphs, Submitted. 
  8. Bollobas, B., Extremal Graph Theory, Academic Press (1978). (1978) Zbl0419.05031MR0506522
  9. Caro, Y., Roditty, Y., On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985), 167-180. (1985) Zbl0623.05031MR0824858
  10. Caro, Y., Roditty, Y., 10.1155/S016117129000031X, J. Math. Math. Sci. 13 (1990), 205-206. (1990) MR1038667DOI10.1155/S016117129000031X
  11. Chartrand, G., Lesniak, L., Graphs and Digraphs (4th ed.), Chapman & Hall, Bocca Raton, FL (2005). (2005) Zbl1057.05001MR2107429
  12. Chartrand, G., Zhang, P., Chromatic Graph Theory, Chapman & Hall, Bocca Raton, FL (2009). (2009) Zbl1169.05001MR2450569
  13. Coffman, W. C., Hakimi, S. L., Schmeichel, E., 10.1016/S0012-365X(02)00569-1, Discrete Math. 263 (2003), 47-59. (2003) Zbl1014.05023MR1955714DOI10.1016/S0012-365X(02)00569-1
  14. Dirac, G. A., 10.1112/jlms/s1-27.1.85, J. Lond. Math. Soc. 27 (1952), 85-92. (1952) Zbl0046.41001MR0045371DOI10.1112/jlms/s1-27.1.85
  15. Dirac, G. A., 10.1007/BF01361708, Math Ann. 153 (1964), 69-80. (1964) MR0160203DOI10.1007/BF01361708
  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. (1980) MR0593902
  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. (2004) 
  18. Haynes, T. W., Hedetniemi, S. T., Slater, P. J., Fundamentals of Domination in Graphs, Marcel Dekker, New York (1998). (1998) Zbl0890.05002MR1605684
  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. (2008) MR2532884
  20. Lick, D. R., White, A. T., 10.4153/CJM-1970-125-1, Canad. J. Math. 22 (1970), 1082-1096. (1970) Zbl0202.23502MR0266812DOI10.4153/CJM-1970-125-1
  21. Łuczak, T., 10.1016/0012-365X(91)90162-U, Discrete Math. 91 (1991), 61-68. (1991) Zbl0752.05046MR1120887DOI10.1016/0012-365X(91)90162-U
  22. McCuaig, W., Shepherd, B., 10.1002/jgt.3190130610, J. Graph Theory 13 (1989), 749-762. (1989) Zbl0708.05058MR1025896DOI10.1002/jgt.3190130610
  23. Ore, O., Theory of Graphs, Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, RI (1962). (1962) Zbl0105.35401MR0150753
  24. Reed, B., 10.1017/S0963548300002042, Combin. Probab. Comput. 5 (1996), 277-295. (1996) Zbl0857.05052MR1411088DOI10.1017/S0963548300002042
  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. (1978) 
  26. Seidman, S. B., 10.1016/0378-8733(83)90028-X, Social Networks 5 (1983), 269-287. (1983) MR0721295DOI10.1016/0378-8733(83)90028-X
  27. Sohn, M. Y., Xudong, Y., 10.4134/JKMS.2009.46.4.759, J. Korean Math. Soc. 46 (2009), 759-773. (2009) MR2532884DOI10.4134/JKMS.2009.46.4.759
  28. Szekeras, G., Wilf, H. S., 10.1016/S0021-9800(68)80081-X, J. Comb. Th. 4 (1968), 1-3. (1968) MR0218269DOI10.1016/S0021-9800(68)80081-X
  29. West, D., Introduction to Graph Theory, (2nd ed.), Prentice Hall of India, New Delhi (2001). (2001) MR1367739
  30. Wilf, H. S., 10.1112/jlms/s1-42.1.330, J. Lond. Math. Soc. 42 (1967), 330-332. (1967) Zbl0144.45202MR0207593DOI10.1112/jlms/s1-42.1.330
  31. Wuchty, S., Almaas, E., 10.1002/pmic.200400962, Proteomics 5 (2005), 444-449. (2005) DOI10.1002/pmic.200400962
  32. Xing, H., Sun, L., Chen, X., 10.1007/s00373-006-0638-3, Graph. Combinator. 22 (2006), 127-143. (2006) Zbl1091.05054MR2221014DOI10.1007/s00373-006-0638-3

NotesEmbed ?

top

You must be logged in to post comments.