Degree Sequences of Monocore Graphs

Allan Bickle

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 3, page 585-592
  • ISSN: 2083-5892

Abstract

top
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 d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .

How to cite

top

Allan Bickle. "Degree Sequences of Monocore Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 585-592. <http://eudml.org/doc/268316>.

@article{AllanBickle2014,
abstract = {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 d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min \{n − 1, k + n − i\} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .},
author = {Allan Bickle},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {monocore graph; degeneracy; degree sequence},
language = {eng},
number = {3},
pages = {585-592},
title = {Degree Sequences of Monocore Graphs},
url = {http://eudml.org/doc/268316},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Allan Bickle
TI - Degree Sequences of Monocore Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 3
SP - 585
EP - 592
AB - 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 d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .
LA - eng
KW - monocore graph; degeneracy; degree sequence
UR - http://eudml.org/doc/268316
ER -

References

top
  1. [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. [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. [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[Crossref][PubMed] 
  4. [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. 
  5. [5] A. Bickle, The k-cores of a Graph (Ph.D. Dissertation, Western Michigan University, 2010). 
  6. [6] A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012) 659-676. doi:10.7151/dmgt.1637[Crossref] Zbl1293.05313
  7. [7] A. Bickle, Cores and shells of graphs, Math. Bohemica 138 (2013) 43-59. Zbl1274.05399
  8. [8] B. Bollobas, Extremal Graph Theory (Academic Press, 1978). 
  9. [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[Crossref] 
  10. [10] G. Chartrand and L. Lesniak, Graphs and Digraphs, (4th Ed.) (CRC Press, 2005). Zbl1057.05001
  11. [11] S. Dorogovtsev, A. Goltsev and J. Mendes, k-core organization of complex networks, Phys. Rev. Lett. 96 (2006).[PubMed][Crossref] Zbl1130.94024
  12. [12] Z. Filáková, P. Mihók and G. Semaniˇsin., A note on maximal k-degenerate graphs, Math. Slovaca 47 (1997) 489-498. 
  13. [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. [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[Crossref] Zbl0202.23502
  15. [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[Crossref] 
  16. [16] J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977) 101-106. Zbl0348.05109
  17. [17] S.B. Seidman, Network structure and minimum degree, Soc. Networks 5 (1983) 269-287. doi:10.1016/0378-8733(83)90028-X[Crossref] 
  18. [18] J.M.S. Simões-Pereira, A survey of k-degenerate graphs, Graph Theory Newsletter 5 (1976) 1-7. Zbl0331.05135
  19. [19] D. West, Introduction to Graph Theory, (2nd Ed.) (Prentice Hall, 2001). 
  20. [20] S. Wuchty and E. Almaas, Peeling the yeast protein network, Proteomics 5 (2005) 444-449. doi:10.1002/pmic.200400962 [Crossref][PubMed] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.