Parallel enumeration of degree sequences of simple graphs II

[1] S. R. Arikati, A. Maheshwari, Realizing degree sequences in parallel, SIAM J. Discrete Math. 9, 2 (1996) 317-338. ⇒25010.1137/S0895480194267932Search in Google Scholar

[2] M. Ascher, Mu torere: an analysis of a Maori game, Math. Mag. 60, 2 (1987) 90-100. ⇒248, 25110.1080/0025570X.1987.11977281Search in Google Scholar

[3] T. M. Barnes, C. D. Savage, A recurrence for counting graphical partitions, Electron. J. Combin. 2 (1995), Research Paper 11, 10 pages (electronic). ⇒25210.37236/1205Search in Google Scholar

[4] T. M. Barnes, C. D. Savage, Efficient generation of graphical partitions, Discrete Appl. Math. 78, 1-3 (1997) 17-26. ⇒25210.1016/S0166-218X(97)00022-XSearch in Google Scholar

[5] M. D. Barrus, Hereditary unigraphs and Erdős-Gallai inequalities. arXiv:1302.2703v1 [mathCO] 12 February 2013, 23 pages. ⇒250Search in Google Scholar

[6] M. D. Barrus, S. G. Hartke, K. F. Jao, D. B. West, Length threshold s for graphic lists given fixed largest and smallest entries and bounded gaps, Discrete Math. 312, 9 (2012) 1494-1501. ⇒25010.1016/j.disc.2011.05.001Search in Google Scholar

[7] E. A. Bender, E. N. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Comb. Math. 24 (1978) 296-307. ⇒25010.1016/0097-3165(78)90059-6Search in Google Scholar

[8] C. Berge, Graphs and Hypergraphs, North Holland, 1973. ⇒246, 250Search in Google Scholar

[9] C. Berge, Graphs (third edition), North Holland, 2001 (first edition: 1989). ⇒ 246, 250Search in Google Scholar

[10] A. Berger, Directed degree sequences, PhD Dissertation, Martin-Luther- Universität Halle-Wittenberg, 2011. http://wcms.uzi.uni-halle.de/download.php?down=22851&elem=2544689. ⇒250Search in Google Scholar

[11] A. Berger, A note on the characterization of digraph sequences, arXiv, arXiv:1112.1215v1 [math.CO] (6 December 2011). ⇒250Search in Google Scholar

[12] A. Berger, A note on the characterization of digraphic sequences, Discrete Math. 314 (2014) 38-41. ⇒25010.1016/j.disc.2013.09.010Search in Google Scholar

[13] A. Berger, M. M¨uller-Hannemann, Uniform sampling of digraphs with a fixed degree sequence, in (ed. D. M. Thilikos) 36th Int. Workshop on Graph Theoretic Concepts in Computer Science (June 28 - 30, 2010, Zarós, Crete, Greece), LNCS 6410 (2010) 220-231. ⇒250Search in Google Scholar

[14] A. Berger, M. M¨uller-Hannemann, Dag characterizations of directed degree sequences, Technical Report 2011/6 of University Halle-Wittenberg, Institute of Computer Science. ⇒25010.1007/978-3-642-22953-4_23Search in Google Scholar

[15] A. Berger, M. M¨uller-Hannemann, How to attack the NP-complete dag realization problems in practice. arXiv, arXiv:1203.36v1, 2012. http://arxiv.org/abs/1203.3636 ⇒250Search in Google Scholar

[16] N. Bödei, Degree sequences of graphs (Hungarian), Mathematical master thesis (supervisor A. Frank), Dept. of Operation Research of Eötvös Loránd University, Budapest, 2010, 43 pages. ⇒246Search in Google Scholar

[17] B. Bollobás, The distribution of the maximum degree of a random graph, DiscreteMath. 32, 2 (1980) 201-203. ⇒25010.1016/0012-365X(80)90054-0Search in Google Scholar

[18] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Comb. 1, 4 (1980) 311-316. ⇒25010.1016/S0195-6698(80)80030-8Search in Google Scholar

[19] B. Bollobás, Degree sequences of random graphs, Discrete Mathematics 33, 1 (1981) 1-19. ⇒25010.1016/0012-365X(81)90253-3Search in Google Scholar

[20] A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Alg. Appl. 33 (1980) 159-231. ⇒25010.1016/0024-3795(80)90105-6Search in Google Scholar

[21] J. C. Brunson, The S-metric, the Beichl-Croteaux approximation and preferential attachment, arXiv:1308.4067v1 [mathCO] 19 August 2013. ⇒250Search in Google Scholar

[22] J. M. Burns, The number of degree sequences of graphs, PhD Dissertation, MIT, 2007. ⇒249, 262Search in Google Scholar

[23] G. Cairns, S. Mendan, An improvement of a result of Zverovich-Zverovich, arXiv arXiv:1303.2144v1 [math.CO], 5 pages. ⇒246Search in Google Scholar

[24] G. Cairns, S. Mendan, Degree sequences for graphs with loops, arXiv arXiv:1303.2145v1 [math.CO], 9 pages. ⇒246Search in Google Scholar

[25] G. Cairns, S. Mendan, Y. Nikolayevsky, A sharp improvement of a result of Zverovich-Zverovich, arXiv arXiv:1310.3992v1 [math.CO], 7 pages. ⇒246Search in Google Scholar

[26] S. A. Choudum, A simple proof of the Erdős-Gallai theorem on graph sequences, Bull. Austral. Math. Soc. 33 (1986) 67-70. ⇒24610.1017/S0004972700002872Search in Google Scholar

[27] V. Chungphaisan, Conditions for sequences to be r-graphic, Discrete Math. 7 (1974) 31-39. ⇒24610.1016/S0012-365X(74)80016-6Search in Google Scholar

[28] N. Cohen, Number of distinct degree sequences among all n-vertex graphs with no isolated vertices: new values for n = 20, 21, 22, and 23, in: ed. by N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2012, http://oeis.org/A095268. ⇒246Search in Google Scholar

[29] P. Das, Characterization of unigraphic and unidigraphic integer-pair sequences, Characterization of unigraphic and unidigraphic integer-pair sequences Discrete Math. 37, 1 (1981) 51-66. ⇒25010.1016/0012-365X(81)90139-4Search in Google Scholar

[30] C. I. Del Genio, H. Kim, Z. Toroczkai, K. E. Bassler, Efficient and exact sampling of simple graphs with given arbitrary degree sequence, PLoS ONE 5, 4 e10012 (2010). ⇒25210.1371/journal.pone.0010012285161520386694Search in Google Scholar

[31] D. Dimitrov, Efficient computation of trees with minimal atom-bound connectivity index. arXiv:1305.1155v2 [csDM] 4 October 2013. ⇒250Search in Google Scholar

[32] P. Erdős, T. Gallai, Graphs with vertices having prescribed degrees (Hungarian), Mat. Lapok 11 (1960) 264-274. ⇒246, 250, 251Search in Google Scholar

[33] P. Erdős, L. B. Richmond, On graphical partitions, Combinatorica 13, 1 (1993) 57-63. ⇒25210.1007/BF01202789Search in Google Scholar

[34] P. L. Erdős, S. Z. Kiss, I. Miklós, On the swap-distances of different realizations of a graphical degree sequence, Comb. Probab. Comp. 22, 3 (2013) 366-383. ⇒ 25010.1017/S0963548313000096Search in Google Scholar

[35] P. L. Erdős, Z. Király, I. Miklós, L. Soukup, Constructive sampling and counting graphical realizations of restricted degree sequences, arXiv arXiv:13017523v3 [math.CO], 24 pages. ⇒250Search in Google Scholar

[36] P. L. Erdős, I. Miklós, Z. Toroczkai, A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, Electron. J. Combin. 17, 1 (2010) R66, 10 pages. ⇒25010.37236/338Search in Google Scholar

[37] P. L. Erdős, I. Miklós, Z. Toroczkai, A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix, arXiv, arXiv:1307.5295v1 [math.CO], 2013, 18 pages. ⇒250Search in Google Scholar

[38] C. Greenhill, A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs, Electron. J. Combin. 18 &P234, 2011, 49 pages. ⇒25010.37236/721Search in Google Scholar

[39] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a simple graph, J. SIAM Appl. Math. 10 (1962) 496-506. ⇒246, 25010.1137/0110037Search in Google Scholar

[40] S. L. Hakimi, On the degrees of the vertices of a graph, F. Franklin Institute 279, 4 (1965) 290-308. ⇒25010.1016/0016-0032(65)90340-6Search in Google Scholar

[41] F. Harary, E. M. Palmer, Graphical Enumeration, Academic Press, New York and London, 1973. ⇒25010.1016/B978-0-12-324245-7.50005-8Search in Google Scholar

[42] V. Havel, A remark on the existence of finite graphs (Czech), Časopis P˘est. Mat. 80 (1955) 477-480. ⇒246, 25010.21136/CPM.1955.108220Search in Google Scholar

[43] P. Hell, D. Kirkpatrick, Linear-time certifying algorithms for near-graphical sequences. Discrete Math. 309, 18 (2009) 5703-5713. ⇒24610.1016/j.disc.2008.05.005Search in Google Scholar

[44] A. Iványi, Reconstruction of complete interval tournaments, Acta Univ. Sapientiae, Inform. 1, 1 (2009) 71-88. ⇒246, 252Search in Google Scholar

[45] A. Iványi, Reconstruction of complete interval tournaments. II, Acta Univ. Sapientiae, Math. 2, 1 (2010) 47-71. ⇒246, 252Search in Google Scholar

[46] A. Iványi, Degree sequences of multigraphs. Annales Univ. Sci. Budapest., Sect. Comp. 37 (2012) 195-214. ⇒246, 250, 252Search in Google Scholar

[47] A. Iványi, L. Lucz, G. Gombos, T. Matuszka C(2n + 1, n + 1): number of ways to put n+1 indistinguishable balls into n+1 distinguishable boxes = number of (n+1)-st degree monomials in n+1 variables = number of monotone maps from 1 . . n + 1 to 1 . . n + 1, in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2013. http://oeis.org/A001700. ⇒247, 262Search in Google Scholar

[48] A. Iványi, L. Lucz, G. Gombos, T. Matuszka The number of degree-vectors for simple graph. in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2013. http://oeis.org/A004251. ⇒246, 251, 259Search in Google Scholar

[49] A. Iványi, L. Lucz, G. Gombos, T. Matuszka, Number of bracelets (turn over necklaces) with n red, 1 pink and n−1 blue beads; also reversible strings with n red and n − 1 blue beads, in (ed. by N. J. A. Sloane), The On-Line Encyclopedia of Integer Sequences, 2013. http://oeis.org/A005654. ⇒262Search in Google Scholar

[50] A. Iványi, L. Lucz, G. Gombos, T. Matuszka, Number of distinct degree sequences among all n-vertex graphs with no isolated vertices: new values for n = 24, 25, 26, 27, 28, and 29, in (ed. by N. J. A. Sloane): The On-Line Encyclopedia of Integer Sequences, 2013, http://oeis.org/A095268. ⇒247, 259Search in Google Scholar

[51] A. Iványi, L. Lucz, T. Matuszka, S. Pirzada, Parallel enumeration of degree sequences of simple graphs. Acta Univ. Sapientiae, Inform. 4, 2 (2012) 260-288. ⇒247, 248, 249, 252, 259Search in Google Scholar

[52] A. Iványi, L. Lucz, T. F. Móri, P. Sótér, On the Erdős-Gallai and Havel-Hakimi algorithms. Acta Univ. Sapientiae, Inform. 3, 2 (2011) 230-268. ⇒245, 246, 247, 248, 249, 250, 251, 252, 257, 259, 262Search in Google Scholar

[53] A. Iványi, S. Pirzada, Comparison based ranking, in: Algorithms of Informatics, Vol. 3 (ed. A. Iványi), AnTonCom, Budapest 2011, 1209-1258. ⇒246Search in Google Scholar

[54] A. Iványi, K. Szabados, Parallel enumeration of degree sequences (Hungarian). Alk. Mat. Lapok, 40 pages, submitted. ⇒258, 259, 263Search in Google Scholar

[55] R. H. Johnson, properties of unique realizations-a survey, Discrete Math. 3, 1 (1980) 185-192. ⇒25010.1016/0012-365X(80)90035-7Search in Google Scholar

[56] J. H. Kim, B. Piztttel, Confirming the Kleitman-Winston conjecture on the largest coefficient in a q-Catalan number, J. Comb. Theory A 99, 2 (2000) 19-206. ⇒25010.1006/jcta.1999.3054Search in Google Scholar

[57] H. Kim, Z. Toroczkai, I. Miklós, P. L. Erdős, L. A. Székely: Degree-based graph construction, J. Physics: Math. Theor. A 42 (2009), 392001, 10 pages. ⇒10.1088/1751-8113/42/39/392001Search in Google Scholar

[58] Z. Király, Recognizing graphic degree sequences and generating all realizations. Egres Technical Reports, TR-2011-11 April 23, 2012, 12 pages. ⇒246, 250Search in Google Scholar

[59] D. J. Kleitman, D. Wang, Algorithms for constructing graphs and digraphs with given valences and factors, Discrete Math. 6 (1973) 79-88. ⇒25010.1016/0012-365X(73)90037-XSearch in Google Scholar

[60] D. J. Kleitman, K. J. Winston, Forests and score vectors. Combinatorica 1 (1981) 49-51. ⇒25010.1007/BF02579176Search in Google Scholar

[61] D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011. ⇒246Search in Google Scholar

[62] M. Koren, Sequences with a unique realization by simple graphs, J. Comb. Theory, Ser. B 21, 3 (1976) 235-244. ⇒25010.1016/S0095-8956(76)80007-XSearch in Google Scholar

[63] M. D. LaMar, Algorithms for realizing degree sequences of directed graphs. arXiv, 2010. http://arxiv.org/abs/0906.0343. ⇒246Search in Google Scholar

[64] V. Librandi, Number of bracelets (turn over necklaces) with n red, 1 pink and n−1 blue beads for n = 1, . . . , 1000, in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2012. http://oeis.org/A005654/b005654.txt ⇒248, 252Search in Google Scholar

[65] X. Lu, S. Bressan, Generating random graph sequences, in (ed. J. X. Yu, M. H. Kim, R. Unland): DASFAA2011, Part I, LNCS 6587, Springer-Verlag, 2011, 570-579. ⇒25210.1007/978-3-642-20149-3_41Search in Google Scholar

[66] L. Lucz, Analysis of degree sequences of graphs (Hungarian), Student thesis awarded by first prize in the Hungarian Scientific Student Conference, Budapest, 2013. Eötvös Loránd University, Faculty of Informatics, Budapest, 2011. http://people.inf.elte.hu/lulsaai/diploma. ⇒252Search in Google Scholar

[67] B. D. McKay, X. Wang, Asymptotic enumeration of tournaments with a given score sequence. J. Comb. Theory A, 73, (1) (1996) 77-90⇒10.1006/jcta.1996.0003Search in Google Scholar

[68] T. Matuszka, Programs and Results Connected with Degree Sequences. ELTE IK, Budapest, 2013. ⇒247, 248, 257, 262Search in Google Scholar

[69] D. Meierling, L. Volkmann, A remark on degree sequences of multigraphs, Math. Methods Operation Research, 69, 2 (2009) 369-374. ⇒24610.1007/s00186-008-0265-2Search in Google Scholar

[70] J. W. Miller, Reduced criteria for degree sequences, Discrete Math. 313, 4 (2013) 550-562. ⇒24610.1016/j.disc.2012.11.027Search in Google Scholar

[71] R. Milo, N. Kashtan, S. Itzkovitz, M.E.J. Newman, U. Alon, On the uniform generation of random graphs with prescribed degree sequences, arXiv, arXiv:condmat/ 0312028v2 [cond-mat.stat-mech], 2004, 4 pages. ⇒250Search in Google Scholar

[72] Miklós, J. Podani, Randomization of presence-absence matrices: comments and new algorithms, Ecology, 85, 1 (2004) 86-92. ⇒250Search in Google Scholar

[73] T. D. Noe, Table of a(n) for n = 1, . . . , 100, in (ed. N. J. A. Sloane): The On- Line Encyclopedia of the Integer Sequences. 2010. http://oeis.org/A001700. ⇒ 252Search in Google Scholar

[74] T. D. Noe, Table of binomial coefficients C(2n − 1, n), in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2012, http://oeis.org/A001791. ⇒252Search in Google Scholar

[75] S. Özkan, Generalization of the Erdős-Gallai inequality. Ars Combin., 98 (2011) 295-302. ⇒246Search in Google Scholar

[76] A. N. Patrinos, S. L. Hakimi, Relations between graphs and integer-pair sequences. Discrete Math., 15, 4 (1976) 347-358 ⇒25010.1016/0012-365X(76)90048-0Search in Google Scholar

[77] S. Pirzada, Introduction to Graph Theory, Universities Press (India) Private Limited, 2012. ⇒246Search in Google Scholar

[78] R. C. Read, The enumeration of locally restricted graphs (I). J. London Math. Soc., 34 (1959) 417-436. ⇒25010.1112/jlms/s1-34.4.417Search in Google Scholar

[79] G. Royle, Is it true that a(n+1)/a(n) tends to 4? In (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2012. http://oeis.org/A095268 ⇒259Search in Google Scholar

[80] F. Ruskey, Number of distinct degree sequences among all n-vertex graphs with no isolated vertices for n = 21, 22 and 23, in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2006. http://oeis.org/A095268. ⇒247Search in Google Scholar

[81] H. J. Ryser, Matrices of zeros and ones. Bull. of Amer. Math. Soc. 66, 6 (1960) 442-464. ⇒25010.1090/S0002-9904-1960-10494-6Search in Google Scholar

[82] R. L. Shuo-Yen, Graphic sequences with unique realization, J. Comb. Theory, Ser. B, 19 (1975) 42-68. ⇒25010.1016/0095-8956(75)90072-6Search in Google Scholar

[83] G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, J. Graph Theory 15, (2) (1991) 223-231. ⇒24610.1002/jgt.3190150209Search in Google Scholar

[84] N. J. A. Sloane, The number of degree-vectors for simple graphs, in (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2011. http: //oeis.org/A004251. ⇒251Search in Google Scholar

[85] N. J. A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995. ⇒248Search in Google Scholar

[86] M. Takahashi, Optimization Methods for Graphical Degree Sequence Problems and their Extensions, PhD thesis, Graduate School of Information, Production and systems, Waseda University, Tokyo, 2007. http://hdl.handle.net/2065/28387. ⇒246Search in Google Scholar

[87] A. Tripathi, H. Tyagy, A simple criterion on degree sequences of graphs. Discrete Appl. Math., 156, 18 (2008) 3513-3517. ⇒24610.1016/j.dam.2008.03.033Search in Google Scholar

[88] A. Tripathi, S. Vijay, A note on a theorem of Erdős & Gallai. Discrete Math., 265, 1-3 (2003) 417-420. ⇒24610.1016/S0012-365X(02)00886-5Search in Google Scholar

[89] A. Tripathi, S. Venugopalan, D. B.West, A short constructive proof of the Erdős- Gallai characterization of graphic lists. Discrete Math., 310, 4 (2010) 833-834. ⇒24610.1016/j.disc.2009.09.023Search in Google Scholar

[90] R. I. Tyshkevich, O. I. Melnikov, V. M. Kotov, On graphs and degree sequences: a canonical decomposition (Russian), Kibernetika 6 (1981) 5-8. ⇒246Search in Google Scholar

[91] K. J. Winston, D. J. Kleitman, On the asymptotic number of tournament score sequences. J. Comb. Theory A 35, 2 (1983) 208-230. ⇒25010.1016/0097-3165(83)90008-0Search in Google Scholar

[92] I. E. Zverovich, V. E. Zverovich, Contributions to the theory of graphic sequences, Discrete Math., 105, 1-3 (1992) 293-303. ⇒24610.1016/0012-365X(92)90152-6Search in Google Scholar