login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011975 Covering numbers C(n,3,2). 11
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 (list; graph; refs; listen; history; text; internal format)
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 J. H. Dinitz and D. R. Stinson, editors,a 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

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. A011977, A001839. A column of A066010. Also a column of A036838.

Sequence in context: A064404 A294488 A047514 * A202112 A079249 A306678

Adjacent sequences:  A011972 A011973 A011974 * A011976 A011977 A011978

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)