A011975 Covering numbers C(n,3,2).

1, 3, 4, 6, 7, 11, 12, 17, 19, 24, 26, 33, 35, 43, 46, 54, 57, 67, 70, 81, 85, 96, 100, 113, 117, 131, 136, 150, 155, 171, 176, 193, 199, 216, 222, 241, 247, 267, 274, 294, 301, 323, 330, 353, 361, 384, 392, 417, 425, 451, 460, 486

Offset

3,2

Comments

Also, minimal number of triangles needed to cover every edge (and node) of a complete graph on n nodes. This problem is also known as the edge clique covering problem. - Dmitry Kamenetsky, Jan 24 2016

References

P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.

CRC Handbook of Combinatorial Designs, 1996, p. 262.

W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

Links

T. D. Noe, Table of n, a(n) for n = 3..1000

Marek Cygan, Marcin Pilipczuk and Michał Pilipczuk, Known algorithms for EDGE CLIQUE COVER are probably optimal, arXiv:1203.1754 [cs.DS], 2012.

Oliver Goldschmidt, Dorit S. Hochbaum, Cor Hurkens and Gang Yu, Approximation Algorithms for the k-Clique Covering Problem, Journal of Discrete Mathematics, volume 9, issue 3, pages 492-509, 1995, doi: 10.1137/S089548019325232X.

D. Gordon, La Jolla Repository of Coverings

Jenö Lehel, The minimum number of triangles covering the edges of a graph, Journal of Graph Theory, volume 13, issue 3, pages 369-384, 1989.

Uenal Mutlu (uenalm(AT)metronet.de), Tables of coverings

Wikipedia, Clique Cover Problem.

Index entries for covering numbers

Formula

Conjecture: G.f. ( -1-2*x-2*x^5+x^7+x^6-x^8 ) / ( (1+x+x^2)*(x^2-x+1)*(1+x)^2*(x-1)^3 ) with a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). - R. J. Mathar, Aug 12 2012

a(n) = ceiling((n/3)*ceiling((n-1)/2)). - Nathaniel Johnston, Jan 10 2024

Maple

L := proc(v, k, t, l) local i, t1; t1 := l; for i from v-t+1 to v do t1 := ceil(t1*i/(i-(v-k))); od: t1; end; # gives Schoenheim bound L_l(v, k, t). Present sequence is L_1(n, 3, 2, 1).

Mathematica

L[v_, k_, t_, m_] := Module[{t1 = m}, Do[t1 = Ceiling[t1*i/(i - (v - k))], {i, v - t + 1, v}]; t1]; Table[L[n, 3, 2, 1], {n, 3, 100}] (* T. D. Noe, Sep 28 2011 *)

Crossrefs

Cf. A011976, A011977, A001839. A column of A066010. Also a column of A036838.

Sequence in context: A335059 A047514 A345716 * A202112 A079249 A306678

Adjacent sequences: A011972 A011973 A011974 * A011976 A011977 A011978

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved