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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices. 14
1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

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

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

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

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

LINKS

Kai Wang, Table of n, a(n) for n = 0..79

A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.

A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, Parallel enumeration of degree sequences of simple graphs II, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 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. Sapiantiae, Inform. 3 (2) (2011) 230-268.

A. Kohnert, Number of different degree sequences of a graph with no isolated vertices, 2016.

Frank Ruskey, Alley CATs in Search of Good Homes

Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.

Eric Weisstein's World of Mathematics, Degree sequence

Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

EXAMPLE

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

From Gus Wiseman, Dec 31 2020: (Start)

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

  ()  .  (1,1)  (2,1,1)  (1,1,1,1)

                (2,2,2)  (2,2,1,1)

                         (2,2,2,2)

                         (3,1,1,1)

                         (3,2,2,1)

                         (3,3,2,2)

                         (3,3,3,3)

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

(End)

MATHEMATICA

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 *)

CROSSREFS

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

Counting the same partitions by sum gives A000569.

Allowing isolated nodes gives A004251.

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

Covering simple graphs are ranked by A309356 and A320458.

Graphical partitions are ranked by A320922.

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

A006125 counts simple graphs, with covering case A006129.

A027187 counts partitions of even length, ranked by A028260.

A058696 counts partitions of even numbers, ranked by A300061.

A339659 is a triangle counting graphical partitions.

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

Sequence in context: A304787 A115117 A029890 * A118397 A171191 A189771

Adjacent sequences:  A095265 A095266 A095267 * A095269 A095270 A095271

KEYWORD

nonn

AUTHOR

Eric W. Weisstein, May 31 2004

EXTENSIONS

Edited by N. J. A. Sloane, Aug 26 2006

More terms from Gordon F. Royle, Aug 21 2006

a(21) and a(22) from Frank Ruskey, Aug 29 2006

a(23) from Frank Ruskey, Aug 31 2006

a(24)-a(29) from Matuszka Tamás, Jan 10 2013

a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016

a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 1 08:23 EST 2021. Contains 341732 sequences. (Running on oeis4.)