login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004251 Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).
(Formerly M1250)
17
1, 1, 2, 4, 11, 31, 102, 342, 1213, 4361, 16016, 59348, 222117, 836315, 3166852, 12042620, 45967479, 176005709, 675759564, 2600672458, 10029832754, 38753710486, 149990133774, 581393603996, 2256710139346, 8770547818956, 34125389919850, 132919443189544, 518232001761434, 2022337118015338, 7898574056034636, 30873421455729728 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

In other words, a(n) = number of graphic sequences of length n, where a graphic sequence is a sequence of numbers which can be the degree sequence of some graph.

In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" in Table 4 on page 260 the values a(30) = 7898574056034638 and a(31) = 30873429530206738 are incorrect due to the incorrect Gz(30) = 5876236938019300 and Gz(31) = 22974847474172100. - Wang Kai, Jun 05 2016

REFERENCES

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978).

LINKS

Wang Kai, Table of n, a(n) for n = 0..79. [Terms 1 through 31 were computed by various authors; terms 32 through 34 by Axel Kohnert and Wang Kai; terms 35 to 79 by Wang Kai]

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).

B. A. Chat, S. Pirzada, A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.

D. Dimitrov, Efficient computation of trees with minimal atom-bond connectivity index, arXiv preprint arXiv:1305.1155 [cs.DM], 2013.

A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapientiae, Inform. 3 (2) (2011) 230-268.

A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 260-288. - From N. J. A. Sloane, Feb 15 2013

A. Ivanyi and J. E. Schoenfield, Deciding football sequences, Acta Univ. Sapientiae, Informatica, 4, 1 (2012) 130-183. - From _N. J. A. Sloane_, Dec 22 2012 [Disclaimer: I am not one of the authors of this paper; I was unpleasantly surprised to find my name on it, as explained here. - Jon E. Schoenfield, Nov 26 2016]

Wang Kai, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms.

P. W. Mills, RP Rundle, VM Dwyer, T Tilma, SJ Devitt, A proposal for an efficient quantum algorithm solving the graph isomorphism problem, - arXiv preprint arXiv 1711.09842, 2017

P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]

Eric Weisstein's World of Mathematics, Degree Sequence.

Wolfram Mathworld, Graphic Sequence

Index entries for sequences related to graphical partitions

FORMULA

G.f. = 1 + x + 2*x^2 + 4*x^3 + 11*x^4 + 31*x^5 + 102*x^6 + 342*x^7 + 1213*x^8 + ...

EXAMPLE

For n = 3 there are 4 different graphic sequences possible: 0 0 0; 1 1 0; 2 1 1; 2 2 2. - Daan van Berkel (daan.v.berkel.1980(AT)gmail.com), Jun 25 2010

CROSSREFS

Cf. A000569, A004250, A029889, A095268.

Sequence in context: A148166 A148167 A148168 * A148169 A110140 A190452

Adjacent sequences:  A004248 A004249 A004250 * A004252 A004253 A004254

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Torsten Sillke, torsten.sillke(AT)lhsystems.com, using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(19) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007

a(20)-a(23) from Nathann Cohen, Jul 09 2011

a(24)-a(29) from Antal Iványi, Nov 15 2011

a(30) and a(31) corrected by Wang Kai, Jun 05 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 01:39 EDT 2018. Contains 316378 sequences. (Running on oeis4.)