A287024 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A287024

Triangle read by rows: T(n,k) is the number of graphs with n vertices with vertex cover number k-1.

1, 1, 1, 1, 2, 1, 1, 3, 6, 1, 1, 4, 15, 13, 1, 1, 5, 30, 82, 37, 1, 1, 6, 51, 301, 578, 106, 1, 1, 7, 80, 842, 4985, 6021, 409, 1, 1, 8, 117, 1995, 27107, 142276, 101267, 1896, 1, 1, 9, 164, 4210, 112225, 1724440, 7269487, 2882460, 12171, 1, 1, 10, 221, 8165, 388547, 13893557, 210799447, 655015612, 138787233, 105070, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

Aside from trailing 1's, same as A115196.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..91 (first 13 rows, after Brendan McKay data in A263341)

Eric Weisstein's World of Mathematics, Vertex Cover

Eric Weisstein's World of Mathematics, Vertex Cover Number

EXAMPLE

Triangle begins:

1, 1;

1, 2, 1;

1, 3, 6, 1;

1, 4, 15, 13, 1;

1, 5, 30, 82, 37, 1;

1, 6, 51, 301, 578, 106, 1;

1, 7, 80, 842, 4985, 6021, 409, 1;

1, 8, 117, 1995, 27107, 142276, 101267, 1896, 1;

1, 9, 164, 4210, 112225, 1724440, 7269487, 2882460, 12171, 1;

...

Row 3 is 1, 2, 1 because

\bar K_3 (1 graph) has vertex cover number 0

K_1\cup K_2 and P_3 (2 graphs) have vertex cover number 1

K_3=C_3 (1 graph) has vertex cover number 2

Here, \bar denotes graph complementation and \cup denotes (disjoint) graph union.

CROSSREFS

Cf. A000088 (row sums), A115196 (number of graphs on n nodes with clique number k), A263341.

Sequence in context: A363007 A144303 A370072 * A107702 A174480 A111670

Adjacent sequences: A287021 A287022 A287023 * A287025 A287026 A287027

KEYWORD

nonn,tabl

AUTHOR

Eric W. Weisstein, May 18 2017

EXTENSIONS

Terms a(46) and beyond from Brendan McKay added by Andrew Howroyd, Feb 19 2020

STATUS

approved