A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

1, 1, 3, 9, 29, 97, 336, 1188, 4275, 15579, 57358, 212908, 795657, 2990221, 11291665, 42814783, 162920417, 621885767, 2380348729

Offset: 0

Author

Gus Wiseman, Dec 27 2020

Keywords

• nonn
• more

Comments

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as half-loop-graphical partitions (A321729). An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex.

The following are equivalent characteristics for any positive integer n:

(1) the prime indices of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops or edges;

(2) n can be factored into distinct primes or squarefree semiprimes;

(3) the prime signature of n is half-loop-graphical.

Examples

			The a(0) = 1 through a(3) = 9 sorted degree sequences:
  ()  (1)  (1,1)  (1,1,1)
           (2,1)  (2,1,1)
           (2,2)  (2,2,1)
                  (2,2,2)
                  (3,1,1)
                  (3,2,1)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(3).
		

Links

• Eric Weisstein's World of Mathematics, Degree Sequence.
• Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Crossrefs

See link for additional cross references.

The version for simple graphs is A004251, covering: A095268.

The non-covering version (it allows isolated vertices) is A029889.

The same partitions counted by sum are conjectured to be A321729.

These graphs are counted by A006125 shifted left, covering: A322661.

The version for full loops is A339844, covering: A339845.

These graphs are ranked by A340018 and A340019.

A006125 counts labeled simple graphs, covering: A006129.

A027187 counts partitions of even length, ranked by A028260.

A058696 counts partitions of even numbers, ranked by A300061.

A320663/A339888 count unlabeled multiset partitions into singletons/pairs.

A339659 counts graphical partitions of 2n into k parts.

Cf. A062740, A096373, A167171, A320461, A320893, A320921, A320923, A338915, A339560, A339841, A339842.

Programs

Mathematica

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{1,2}]],Union@@#==Range[n]&]]],{n,0,5}]

Formula

a(n) = A029889(n) - A029889(n-1) for n > 0. - Andrew Howroyd, Jan 10 2024

Extensions

a(7)-a(18) added (using A029889) by Andrew Howroyd, Jan 10 2024