A327071 -id:A327071 - cp's OEIS frontend

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

0, 0, 1, 3, 28, 475, 14646, 813813, 82060392, 15251272983, 5312295240010, 3519126783483377, 4487168285715524124, 11116496280631563128723, 53887232400918561791887118, 513757147287101157620965656285, 9668878162669182924093580075565776

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

A graph is covering if the vertex set is the union of the edge set, so there are no isolated vertices.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 28 connected covering graphs with at least one endpoint.

The non-connected version is A327227.
The non-covering version is A327364.
Graphs with endpoints are A245797.
Connected covering graphs are A001187.
Connected graphs with bridges are A327071.
Cf. A004110, A059166, A006125, A006129, A059166, A100743, A141580, A322395, A327105, A327229, A327230, A327366, A327369, A327377.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

seq(n)={Vec(serlaplace(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k! + O(x*x^n))) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Inverse binomial transform of A327364.

a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

A327235 Number of unlabeled simple graphs with n vertices whose edge-set is not connected.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 14, 49, 234, 1476, 15405, 307536, 12651788, 1044977929, 167207997404, 50838593828724, 29156171171238607, 31484900549777534887, 64064043979274771429379, 246064055301339083624989655, 1788069981480210465772374023323, 24641385885409824180500407923934750

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

			The a(4) = 2 through a(6) = 14 edge-sets:
  {}       {}             {}
  {12,34}  {12,34}        {12,34}
           {12,35,45}     {12,34,56}
           {12,34,35,45}  {12,35,45}
                          {12,34,35,45}
                          {12,35,46,56}
                          {12,36,46,56}
                          {13,23,46,56}
                          {12,34,35,46,56}
                          {12,36,45,46,56}
                          {13,23,45,46,56}
                          {12,13,23,45,46,56}
                          {12,35,36,45,46,56}
                          {12,34,35,36,45,46,56}

Unlabeled non-connected graphs are A000719.
Partial sums of A327075.
The labeled version is A327199.
Cf. A000088, A001349, A002494, A052446, A054592, A327070, A327071.

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A327235(n):
    if n == 0: return 1
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    def a(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n if n else 1
    return 1+b(n)-sum(a(i) for i in range(1,n+1)) # Chai Wah Wu, Jul 03 2024

a(n) = 1 + A000088(n) - Sum_{i = 1..n} A001349(i).

a(20)-a(21) from Chai Wah Wu, Jul 03 2024

A327357 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of sets covering n vertices with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 3, 1, 30, 13, 33, 32, 6, 546, 421, 1302, 1915, 1510, 693, 316, 135, 45, 10, 1

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.

The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty set-system.

			Triangle begins:
    1
    0    1
    1    1
    4    1    3    1
   30   13   33   32    6
  546  421 1302 1915 1510  693  316  135   45   10    1
Row n = 3 counts the following antichains:
  {{1},{2,3}}    {{1,2,3}}  {{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
  {{2},{1,3}}               {{1,2},{2,3}}
  {{3},{1,2}}               {{1,3},{2,3}}
  {{1},{2},{3}}

Row sums are A307249.
Column k = 0 is A120338.
The non-covering version is A327353.
The version for spanning edge-connectivity is A327352.
The specialization to simple graphs is A327149, with unlabeled version A327201.
Cf. A014466, A293606, A326704, A326787, A327071, A327148, A327236, A327351.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,5},{k,0,2^n}]//.{foe___,0}:>{foe}

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 6, 46, 655, 17991, 927416, 89009740, 16020407709, 5468601546685, 3578414666656214, 4529751815161579194, 11175105490563109463875, 54043272967471942825421219, 514566625051705610110588073460, 9677104749727084630538798805505880

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

			The a(4) = 46 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}
  {13}  {12,14}  {12,13,24}  {12,13,14,24}
  {14}  {12,23}  {12,13,34}  {12,13,14,34}
  {23}  {12,24}  {12,14,23}  {12,13,23,24}
  {24}  {13,14}  {12,14,34}  {12,13,23,34}
  {34}  {13,23}  {12,23,24}  {12,14,23,24}
        {13,34}  {12,23,34}  {12,14,24,34}
        {14,24}  {12,24,34}  {12,23,24,34}
        {14,34}  {13,14,23}  {13,14,23,34}
        {23,24}  {13,14,24}  {13,14,24,34}
        {23,34}  {13,23,24}  {13,23,24,34}
        {24,34}  {13,23,34}  {14,23,24,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The covering case is A327362.
Graphs with endpoints are A245797.
Graphs with connected edge-set are A287689.
Connected graphs with bridges are A327071.
Covering graphs with endpoints are A327227.
Cf. A001187, A059167, A141580, A322395, A327148, A327335, A327369.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

seq(n)={my(x=x + O(x*x^n)); Vec(serlaplace(exp(x)*(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!)) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x))^k/k!)))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Binomial transform of A327362.

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

A327438 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 3, 1, 6, 2, 1, 15, 7, 5, 2, 52, 53, 62, 31, 9, 1, 1

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other.

The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices.

			Triangle begins:
   1
   1  1
   3  1
   6  2  1
  15  7  5  2
  52 53 62 31  9  1  1
The antichains counted in row n = 4 are the following:
  0             {1234}         {12}{134}{234}     {123}{124}{134}{234}
  {1}           {12}{134}      {123}{124}{134}    {12}{13}{14}{23}{24}{34}
  {12}          {123}{124}     {12}{13}{24}{34}
  {123}         {12}{13}{14}   {12}{13}{14}{234}
  {1}{2}        {12}{13}{24}   {12}{13}{14}{23}{24}
  {1}{23}       {12}{13}{234}
  {12}{13}      {12}{13}{14}{23}
  {1}{234}
  {12}{34}
  {1}{2}{3}
  {1}{2}{34}
  {2}{13}{14}
  {12}{13}{23}
  {1}{2}{3}{4}
  {4}{12}{13}{23}

Row sums are A306505.
Column k = 0 is A327437.
The labeled version is A327352.
Cf. A014466, A052446, A327062, A327071, A327103, A327111, A327144, A327352, A327353.

A327110 BII-numbers of set-systems with spanning edge-connectivity 3.

Original entry on oeis.org

116, 117, 118, 119, 124, 125, 126, 127, 1796, 1797, 1798, 1799, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914, 1915, 1916, 1917, 1918, 1919, 1924, 1925, 1926, 1927, 2032, 2033, 2034, 2035, 2036, 2037, 2038, 2039, 2040, 2041, 2042, 2043, 2044

Offset: 1

Gus Wiseman, Oct 03 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices.

			The sequence of all set-systems with spanning edge-connectivity 3 together with their BII-numbers begins:
   116: {{1,2},{1,3},{2,3},{1,2,3}}
   117: {{1},{1,2},{1,3},{2,3},{1,2,3}}
   118: {{2},{1,2},{1,3},{2,3},{1,2,3}}
   119: {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
   124: {{1,2},{3},{1,3},{2,3},{1,2,3}}
   125: {{1},{1,2},{3},{1,3},{2,3},{1,2,3}}
   126: {{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
   127: {{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
  1796: {{1,2},{1,4},{2,4},{1,2,4}}
  1797: {{1},{1,2},{1,4},{2,4},{1,2,4}}
  1798: {{2},{1,2},{1,4},{2,4},{1,2,4}}
  1799: {{1},{2},{1,2},{1,4},{2,4},{1,2,4}}
  1904: {{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1905: {{1},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1906: {{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1907: {{1},{2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1908: {{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1909: {{1},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1910: {{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}
  1911: {{1},{2},{1,2},{1,3},{2,3},{1,2,3},{1,4},{2,4},{1,2,4}}

Positions of 3's in A327144.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
BII-numbers for spanning edge-connectivity 1 are A327111.
Cf. A001187, A095983, A322395, A326749, A326753, A326787, A327069, A327071, A327103, A327130, A327146, A327147.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Select[Range[1000],spanEdgeConn[Union@@bpe/@bpe[#],bpe/@bpe[#]]==3&]

cp's OEIS Frontend

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A327235 Number of unlabeled simple graphs with n vertices whose edge-set is not connected.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

Extensions

A327357 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of sets covering n vertices with non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A327438 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327110 BII-numbers of set-systems with spanning edge-connectivity 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica