Degree sequences of monocore graphs. (English) Zbl 1295.05192

Summary: A \(k\)-monocore graph is a graph which has its minimum degree and degeneracy both equal to \(k\). Integer sequences that can be the degree sequence of some \(k\)-monocore graph are characterized as follows: A nonincreasing sequence of integers \(d_{0},\dots, d_{n}\) is the degree sequence of some \(k\)-monocore graph \(G\), \(0 \leq k \leq n-1\), if and only if \(k \leq d_{i} \leq \min \{n - 1, k + n - i\}\) and \(\sum d_{i} = 2m\), where \(m\) satisfies \(\lceil \frac{k\cdot n}{2} \rceil\leq m \leq k \cdot n - {k+1 \choose 2}\).


05C75 Structural characterization of families of graphs
05C07 Vertex degrees


Full Text: DOI


[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] J. Alvarez-Hamelin, L. Dall’Asta, A. Barrat, A. Vespignani, k-core decomposition: a tool for the visualization of large scale networks, Adv. Neural Inf. Process. Syst. 18 (2006) 41.
[3] G. Bader, C. Hogue, An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics 4 (2003). doi:10.1186/1471-2105-4-2
[4] V. Batagelj and M. Zaversnik, An O(m) algorithm for cores decomposition of net- works. http://vlado.fmf.uni-lj.si/pub/networks/doc/cores/cores.pdf. (2002) Last accessed November 25, 2011. · Zbl 1284.05252
[5] A. Bickle, The k-cores of a Graph (Ph.D. Dissertation, Western Michigan University, 2010).
[6] A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012) 659-676. doi:10.7151/dmgt.1637 · Zbl 1293.05313
[7] A. Bickle, Cores and shells of graphs, Math. Bohemica 138 (2013) 43-59. · Zbl 1274.05399
[8] B. Bollobas, Extremal Graph Theory (Academic Press, 1978). · Zbl 0419.05031
[9] M. Borowiecki, J. Ivanˇco, P. Mih´ok and G. Semaniˇsin, Sequences realizable by max- imal k-degenerate graphs, J. Graph Theory 19 (1995) 117-124. doi:10.1002/jgt.3190190112 · Zbl 0813.05061
[10] G. Chartrand and L. Lesniak, Graphs and Digraphs, (4th Ed.) (CRC Press, 2005).
[11] S. Dorogovtsev, A. Goltsev and J. Mendes, k-core organization of complex networks, Phys. Rev. Lett. 96 (2006).
[12] Z. Filáková, P. Mihók and G. Semaniˇsin., A note on maximal k-degenerate graphs, Math. Slovaca 47 (1997) 489-498. · Zbl 0937.05040
[13] M. Gaertler and M. Patrignani, Dynamic analysis of the autonomous system graph, Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (2004) 13-24.
[14] D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096. doi:10.4153/CJM-1970-125-1 · Zbl 0202.23502
[15] T. Luczak, 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
[16] J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977) 101-106. · Zbl 0348.05109
[17] S.B. Seidman, Network structure and minimum degree, Soc. Networks 5 (1983) 269-287. doi:10.1016/0378-8733(83)90028-X
[18] J.M.S. Simões-Pereira, A survey of k-degenerate graphs, Graph Theory Newsletter 5 (1976) 1-7. · Zbl 0331.05135
[19] D. West, Introduction to Graph Theory, (2nd Ed.) (Prentice Hall, 2001).
[20] S. Wuchty and E. Almaas, Peeling the yeast protein network, Proteomics 5 (2005) 444-449. doi:10.1002/pmic.200400962
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.