The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices. 6


%S 1,2,7,20,71,240,871,3148,11655,43332,162769,614198,2330537,8875768,

%T 33924859,130038230,499753855,1924912894,7429160296,28723877732,

%U 111236423288,431403470222,1675316535350,6513837679610,25354842100894,98794053269694,385312558571890,1504105116253904,5876236938019298,22974847399695092

%N Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

%C A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.

%C Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - _Paul D. Hanna_, Aug 18 2006

%C Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - _Gordon F. Royle_, Aug 29 2006

%C Previous values a(30) = 5876236938019300 from _Lorand Lucz_, Jul 07 2013 and a(31) = 22974847474172100 from _Lorand Lucz_, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed _Kai Wang_ and Axel Kohnert. - _Vaclav Kotesovec_, Apr 15 2016

%C In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - _Vaclav Kotesovec_, Apr 15 2016

%H Kai Wang, <a href="/A095268/b095268.txt">Table of n, a(n) for n = 2..79</a>

%H A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, <a href="http://www.acta.sapientia.ro/acta-info/C4-2/info42-7.pdf">Parallel enumeration of degree sequences of simple graphs</a>, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.

%H A. Iványi, G. Gombos, L. Lucz, T. Matuszka, <a href="http://dx.doi.org/10.2478/ausi-2014-0013">Parallel enumeration of degree sequences of simple graphs II</a>, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 2013).

%H A. Iványi, L. Lucz, T. F. Móri and P. Sótér, <a href="http://www.acta.sapientia.ro/acta-info/C3-2/info32-7.pdf">On Erdős-Gallai and Havel-Hakimi algorithms</a>, Acta Univ. Sapiantiae, Inform. 3 (2) (2011) 230-268.

%H A. Kohnert, <a href="http://www.mathe2.uni-bayreuth.de/axel/magdeburg06_number_of_different_degree_sequences.pdf">Number of different degree sequences of a graph with no isolated vertices</a>, 2016.

%H Frank Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/AlleyCat/AlleyCat.html">Alley CATs in Search of Good Homes</a>

%H Kai Wang, <a href="http://arxiv.org/abs/1604.04148">Efficient Counting of Degree Sequences</a>, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DegreeSequence.html">Degree sequence</a>

%e a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.

%Y Cf. A000569, A002494, A004250, A007721 (analog for connected graphs), A271831.

%K nonn

%O 2,2

%A _Eric W. Weisstein_, May 31 2004

%E Edited by _N. J. A. Sloane_, Aug 26 2006

%E More terms from _Gordon F. Royle_, Aug 21 2006

%E a(21) and a(22) from _Frank Ruskey_, Aug 29 2006

%E a(23) from _Frank Ruskey_, Aug 31 2006

%E a(24)-a(29) from _Matuszka Tamás_, Jan 10 2013

%E a(30)-a(31) from articles by _Kai Wang_ and Axel Kohnert, Apr 15 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 1 03:22 EDT 2020. Contains 333155 sequences. (Running on oeis4.)