Parallel enumeration of degree sequences of simple graphs II

Antal Iványi; Gergő Gombos; Loránd Lucz; Tamás Matuszka

doi:10.2478/ausi-2014-0013

Abstract

In the paper we report on the parallel enumeration of the degree sequences (their number is denoted by G(n)) and zerofree degree sequences (their number is denoted by (Gz(n)) of simple graphs on n = 30 and n = 31 vertices. Among others we obtained that the number of zerofree degree sequences of graphs on n = 30 vertices is G_z(30) = 5 876 236 938 019 300 and on n = 31 vertices is G_z(31) = 22 974 847 474 172 374. Due to Corollary 21 in [52] these results give the number of degree sequences of simple graphs on 30 and 31 vertices.

References

[1] S. R. Arikati, A. Maheshwari, Realizing degree sequences in parallel, SIAM J. Discrete Math. 9, 2 (1996) 317-338. ⇒25010.1137/S0895480194267932
Search 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.11977281
Search 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/1205
Search 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-X
Search in Google Scholar
[5] M. D. Barrus, Hereditary unigraphs and Erdős-Gallai inequalities. arXiv:1302.2703v1 [mathCO] 12 February 2013, 23 pages. ⇒250
Search 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.001
Search 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-6
Search in Google Scholar
[8] C. Berge, Graphs and Hypergraphs, North Holland, 1973. ⇒246, 250
Search in Google Scholar
[9] C. Berge, Graphs (third edition), North Holland, 2001 (first edition: 1989). ⇒ 246, 250
Search 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. ⇒250
Search in Google Scholar
[11] A. Berger, A note on the characterization of digraph sequences, arXiv, arXiv:1112.1215v1 [math.CO] (6 December 2011). ⇒250
Search 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.010
Search 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. ⇒250
Search 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_23
Search 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 ⇒250
Search 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. ⇒246
Search 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-0
Search 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-8
Search 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-3
Search 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-6
Search in Google Scholar
[21] J. C. Brunson, The S-metric, the Beichl-Croteaux approximation and preferential attachment, arXiv:1308.4067v1 [mathCO] 19 August 2013. ⇒250
Search in Google Scholar
[22] J. M. Burns, The number of degree sequences of graphs, PhD Dissertation, MIT, 2007. ⇒249, 262
Search in Google Scholar
[23] G. Cairns, S. Mendan, An improvement of a result of Zverovich-Zverovich, arXiv arXiv:1303.2144v1 [math.CO], 5 pages. ⇒246
Search in Google Scholar
[24] G. Cairns, S. Mendan, Degree sequences for graphs with loops, arXiv arXiv:1303.2145v1 [math.CO], 9 pages. ⇒246
Search 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. ⇒246
Search 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/S0004972700002872
Search 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-6
Search 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. ⇒246
Search 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-4
Search 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.0010012285161520386694
Search in Google Scholar
[31] D. Dimitrov, Efficient computation of trees with minimal atom-bound connectivity index. arXiv:1305.1155v2 [csDM] 4 October 2013. ⇒250
Search in Google Scholar
[32] P. Erdős, T. Gallai, Graphs with vertices having prescribed degrees (Hungarian), Mat. Lapok 11 (1960) 264-274. ⇒246, 250, 251
Search in Google Scholar
[33] P. Erdős, L. B. Richmond, On graphical partitions, Combinatorica 13, 1 (1993) 57-63. ⇒25210.1007/BF01202789
Search 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/S0963548313000096
Search 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. ⇒250
Search 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/338
Search 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. ⇒250
Search 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/721
Search 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/0110037
Search 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-6
Search 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-8
Search 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.108220
Search 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.005
Search in Google Scholar
[44] A. Iványi, Reconstruction of complete interval tournaments, Acta Univ. Sapientiae, Inform. 1, 1 (2009) 71-88. ⇒246, 252
Search in Google Scholar
[45] A. Iványi, Reconstruction of complete interval tournaments. II, Acta Univ. Sapientiae, Math. 2, 1 (2010) 47-71. ⇒246, 252
Search in Google Scholar
[46] A. Iványi, Degree sequences of multigraphs. Annales Univ. Sci. Budapest., Sect. Comp. 37 (2012) 195-214. ⇒246, 250, 252
Search 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, 262
Search 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, 259
Search 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. ⇒262
Search 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, 259
Search 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, 259
Search 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, 262
Search 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. ⇒246
Search in Google Scholar
[54] A. Iványi, K. Szabados, Parallel enumeration of degree sequences (Hungarian). Alk. Mat. Lapok, 40 pages, submitted. ⇒258, 259, 263
Search 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-7
Search 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.3054
Search 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/392001
Search 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, 250
Search 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-X
Search in Google Scholar
[60] D. J. Kleitman, K. J. Winston, Forests and score vectors. Combinatorica 1 (1981) 49-51. ⇒25010.1007/BF02579176
Search in Google Scholar
[61] D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011. ⇒246
Search 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-X
Search in Google Scholar
[63] M. D. LaMar, Algorithms for realizing degree sequences of directed graphs. arXiv, 2010. http://arxiv.org/abs/0906.0343. ⇒246
Search 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, 252
Search 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_41
Search 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. ⇒252
Search 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.0003
Search in Google Scholar
[68] T. Matuszka, Programs and Results Connected with Degree Sequences. ELTE IK, Budapest, 2013. ⇒247, 248, 257, 262
Search 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-2
Search 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.027
Search 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. ⇒250
Search in Google Scholar
[72] Miklós, J. Podani, Randomization of presence-absence matrices: comments and new algorithms, Ecology, 85, 1 (2004) 86-92. ⇒250
Search 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. ⇒ 252
Search 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. ⇒252
Search in Google Scholar
[75] S. Özkan, Generalization of the Erdős-Gallai inequality. Ars Combin., 98 (2011) 295-302. ⇒246
Search 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-0
Search in Google Scholar
[77] S. Pirzada, Introduction to Graph Theory, Universities Press (India) Private Limited, 2012. ⇒246
Search 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.417
Search 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 ⇒259
Search 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. ⇒247
Search 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-6
Search 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-6
Search 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.3190150209
Search 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. ⇒251
Search in Google Scholar
[85] N. J. A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995. ⇒248
Search 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. ⇒246
Search 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.033
Search 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-5
Search 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.023
Search 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. ⇒246
Search 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-0
Search 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-6
Search in Google Scholar

Parallel enumeration of degree sequences of simple graphs II

Abstract

Paradigm

My account