Libro (grafeteorio)

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Libro (grafeteorio).png

En grafeteorio, libro (kutime skribata kiel Bp) estas fendebla grafeo konsistanta el p trianguloj havantaj komunan lateron (sciatan kiel la "bazo" de la libro). Por donita grafeo G, kiel bk(G) estas ofte skribata la plej granda libro enhavata en G.

Antaŭe, la libro estadis skribata kiel Ke(2, p). Estu K(m, n) la plena dukolora grafeo kun ampleksoj de la koloraj partoj m kaj n. Tiam Ke(m, n) estas difinita kiel K(m, n) kun superflua latero en la unua dispartigo. Ĝi povas ankaŭ esti konsiderata kiel plena trikolora grafeo K(1, 1, p).

Propraĵoj[redakti | redakti fonton]

Ĉi tie r(Bp, Bq) estas la nombro de Ramsey inter du libroj.

  • Se 1≤p≤q, do r(Bp, Bq)=2q+3 (pruvita de Rousseau kaj Sheehan).
  • Ekzistas konstanto c=o(1) tia ke se cp≤q do r(Bp, Bq)=2q+3.
  • Se p≤q/6+o(q) kaj q estas granda do r(Bp, Bq)=2q+3.
  • Estu C konstanto kaj k = Cn. Tiam ĉiu grafeo kun n verticoj kaj m lateroj enhavas Bk. (???)