|
|
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
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023
|
|
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.
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
|
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
Graphical partitions are ranked by A320922.
A339659 is a triangle counting graphical partitions.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
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
|
|
|
|