A011976 -id:A011976 - cp's OEIS frontend

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

N. J. A. Sloane

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

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.

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

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

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).

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 *)

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

A240115 Schoenheim lower bound L(n,4,2).

Original entry on oeis.org

1, 3, 3, 4, 6, 7, 8, 11, 12, 13, 18, 19, 20, 26, 27, 29, 35, 37, 39, 46, 48, 50, 59, 61, 63, 73, 75, 78, 88, 91, 94, 105, 108, 111, 124, 127, 130, 144, 147, 151, 165, 169, 173, 188, 192, 196, 213, 217, 221, 239, 243, 248, 266, 271, 276, 295, 300, 305, 326

Offset: 4

Colin Barker, Apr 01 2014

Only differs from A011976 when n = 7, 9, 10, or 19. - Nathaniel Johnston, Jan 10 2024

Colin Barker, Table of n, a(n) for n = 4..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240116, A240117, A240118, A240119.

Cf. A011975, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 4, 2], {n, 4, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=4, 100, s=concat(s, schoenheim(n, 4, 2))); s

Empirical g.f.: x^4*(x^15 -x^13 -x^12 +2*x^10 +x^7 +x^5 +2*x +1) / ( -x^16 +x^15 +x^13 -x^12 +x^4 -x^3 -x +1).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula