A095268 - OEIS

%I #97 Feb 22 2023 04:45:28

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

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

%U 28723877732,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

%C The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - _Tom Johnston_, Jan 18 2023

%H Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, <a href="/A095268/b095268.txt">Table of n, a(n) for n = 0..1651</a> (terms 0 through 79 from Kai Wang)

%H Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, <a href="https://arxiv.org/abs/2301.07022">Counting graphic sequences via integrated random walks</a>, arXiv:2301.07022 [math.CO], 2023.

%H A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, <a href="https://acta.sapientia.ro/en/series/informatica/publications/informatica-contents-of-volume-4-number-2-2012/parallel-enumeration-of-degree-sequences-of-simple-graphs">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, and 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>

%H Gus Wiseman, <a href="/A339741/a339741_1.txt">Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.</a>

%F a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - _Tom Johnston_, Jan 18 2023

%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.

%e From _Gus Wiseman_, Dec 31 2020: (Start)

%e The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):

%e   ()  .  (1,1)  (2,1,1)  (1,1,1,1)

%e                 (2,2,2)  (2,2,1,1)

%e                          (2,2,2,2)

%e                          (3,1,1,1)

%e                          (3,2,2,1)

%e                          (3,3,2,2)

%e                          (3,3,3,3)

%e For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).

%e (End)

%t Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* _Gus Wiseman_, Dec 31 2020 *)

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

%Y Counting the same partitions by sum gives A000569.

%Y Allowing isolated nodes gives A004251.

%Y The version with half-loops is A029889, with covering case A339843.

%Y Covering simple graphs are ranked by A309356 and A320458.

%Y Graphical partitions are ranked by A320922.

%Y The version with loops is A339844, with covering case A339845.

%Y A006125 counts simple graphs, with covering case A006129.

%Y A027187 counts partitions of even length, ranked by A028260.

%Y A058696 counts partitions of even numbers, ranked by A300061.

%Y A339659 is a triangle counting graphical partitions.

%Y Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

%K nonn

%O 0,4

%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

%E a(0) = 1 and a(1) = 0 prepended by _Gus Wiseman_, Dec 31 2020