Carte (teoria graficelor)

O carte (deseori scrisă ) poate fi orice grafic de un fel care este format din cicluri care împărtășesc o margine. $B_{p}$

Variante

Un fel, care poate fi numit o carte de quads , constă din p quad -uri care au o margine (cunoscută ca „coloana vertebrală” sau „baza” cărții). Adică este un produs direct al unei stele și al unei singure muchii [1] [2] . O carte de 7 pagini de acest tip oferă un exemplu de grafic fără marcaj armonic [2] .

Al doilea fel, care poate fi numit o carte de triunghiuri sau o carte triunghiulară , este graficul bipartit complet K 1,1, p . Acesta este un grafic format din triunghiuri având o muchie comună [3] . O carte de acest tip este un grafic divizat . Acest grafic poate fi numit și [4] . Cărțile triunghiulare formează unul dintre elementele cheie ale graficelor cu margini perfecte [5] . $p$ $K_{e}(2,p)$

Termenul „carte grafică” a fost folosit în alte scopuri. Astfel, Barioli [6] l-a folosit pentru grafuri compuse din subgrafe arbitrare care au două vârfuri comune. (Barioli nu a folosit notația pentru aceste grafice de carte.) $B_{p}$

În interiorul graficelor mari

Având în vedere un grafic , se poate scrie pentru cea mai mare carte (de tipul în cauză) conținută în . $G$ $bk(G)$ $G$

Teoreme despre cărți

Să notăm numărul Ramsey a două cărți triunghiulare . Acesta este cel mai mic număr astfel încât, pentru un graf acerbă cu vârfuri, fie graficul însuși conține ca subgraf, fie complementul său conține ca subgraf. $r(B_{p},\B_{q}).$ $r$ $r$ $B_{p}$ $B_{q)$

Dacă , atunci (demonstrat de Rousseau și Shihan). $1\leqslant p\leqslant q$ $r(B_{p},\B_{q})=2q+3$
Există o constantă astfel încât atunci când . $c=o(1)$ $r(B_{p},\B_{q})=2q+3$ $q\geqslant cp$
Dacă și este suficient de mare, numărul Ramsey este dat de . $p\leqslant q/6+o(q)$ $q$ $2q+3$
Fie o constantă și . Atunci orice grafic cu vârfuri și muchii conține (o carte de triunghiuri) [7] . $C$ $k=Cn$ $n$ $m$ $B_{k}$

Note

^ Weisstein , Eric W. Book Graph pe site- ul Wolfram MathWorld .
↑ 1 2 Gallian, 1998 , p. Sondaj dinamic 6.
↑ Shi, Song, 2007 , p. 526-529.
↑ Erdős, 1963 , p. 156–160.
↑ Maffray, 1992 , p. 1–8.
↑ Barioli, 1998 , p. 11–31.
↑ Erdős, 1962 , p. 122-127.

Literatură

Iosif Gallian. Un studiu dinamic al etichetării graficelor // Electronic Journal of Combinatorics . - 1998. - T. 5 .
Lingsheng Shi, Zhipeng Song. Limitele superioare ale razei spectrale ale graficelor fără carte și/sau K 2,l -// Algebra liniară și aplicațiile sale. - 2007. - T. 420 . - doi : 10.1016/j.laa.2006.08.007 .
Paul Erds . Despre structura graficelor liniare // Israel Journal of Mathematics. - 1963. - T. 1 . - doi : 10.1007/BF02759702 .
Frederic Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory . - 1992. - T. 55 , nr. 1 . — S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V .
Francesco Barioli. Matrici complet pozitive cu un grafic de carte // Algebră liniară și aplicațiile sale. - 1998. - T. 277 . - doi : 10.1016/S0024-3795(97)10070-2 .
Erdős P. Despre o teoremă a lui Rademacher-Turán // Illinois Journal of Mathematics. - 1962. - T. 6 .