Kirja (graafiteoria)

Kirja (usein kirjoitettu ) voi olla mikä tahansa graafi, joka muodostuu syklistä, joilla on yhteinen reuna. $B_{p}$

Muunnelmia

Eräs laji, jota voidaan kutsua nelosten kirjaksi , koostuu p nelosista , joilla on yhteinen reuna (tunnetaan kirjan "selkärankana" tai "pohjana"). Eli se on tähden ja yhden reunan suora tulo [1] [2] . Tämän tyyppinen 7-sivuinen kirja antaa esimerkin graafista ilman harmonista merkintää [2] .

Toinen laji, jota voidaan kutsua kolmioiden kirjaksi tai kolmiokirjaksi , on täydellinen kaksiosainen graafi K 1,1, p . Tämä on graafi, joka koostuu kolmioista , joilla on yhteinen reuna [3] . Tämän tyyppinen kirja on jaettu graafi . Tätä kuvaajaa voidaan kutsua myös nimellä [4] . Kolmiokirjat muodostavat yhden reunaperfect-graafien tärkeimmistä rakennuspalikoista [5] . $s$ $K_{e}(2,p)$

Termiä "kaaviokirja" on käytetty muihin tarkoituksiin. Näin ollen Barioli [6] käytti sitä mielivaltaisista osagraafista koostuville graafiille, joilla on kaksi yhteistä kärkeä. (Barioli ei käyttänyt merkintää näissä kirjakaavioissa.) $B_{p}$

Suurten kaavioiden sisällä

Kun kaavio on annettu , voidaan kirjoittaa suurimmalle kirjalle (kyseisen tyypin), joka sisältyy . $G$ $bk(G)$ $G$

Lauseet kirjoista

Merkitään kahden kolmiomaisen kirjan Ramsey-lukua, joka on pienin sellainen luku , että kovassa graafissa, jossa on pisteet, joko itse graafi sisältää aligraafina tai sen komplementti sisältää aligraafina. $r(B_{p},\ B_{q}).$ $r$ $r$ $B_{p}$ ${\näyttötyyli B_{q))$

Jos , niin (Todistivat Rousseau ja Shihan). $1\leqslant p\leqslant q$ $r(B_{p},\ B_{q})=2q+3$
On olemassa sellainen vakio , että kun . $c=o(1)$ $r(B_{p},\ B_{q})=2q+3$ $q\geqslant cp$
Jos ja on riittävän suuri, Ramsey-luku saadaan kaavalla . $p\leqslant q/6+o(q)$ $q$ $2q+3$
Antaa olla vakio, ja . Silloin mikä tahansa graafi, jossa on pisteitä ja reunoja, sisältää (kolmioiden kirjan) [7] . $C$ $k=Cn$ $n$ $m$ $B_{k}$

Muistiinpanot

↑ Weisstein, Eric W. Book Graph Wolfram MathWorld -verkkosivustolla .
↑ 1 2 Gallian, 1998 , s. Dynaaminen kysely 6.
↑ Shi, Song, 2007 , s. 526-529.
↑ Erdős, 1963 , s. 156-160.
↑ Maffray, 1992 , s. 1–8.
↑ Barioli, 1998 , s. 11–31.
↑ Erdős, 1962 , s. 122-127.

Kirjallisuus

Joseph Gallian. Dynaaminen kaaviomerkintöjen tutkimus // Electronic Journal of Combinatorics . - 1998. - T. 5 .
Lingsheng Shi, Zhipeng Song. Kirjattomien ja/tai K 2,l -vapaiden graafien spektrisäteen ylärajat // Lineaarinen algebra ja sen sovellukset. - 2007. - T. 420 . - doi : 10.1016/j.laa.2006.08.007 .
Paul Erds . Lineaaristen graafien rakenteesta // Israel Journal of Mathematics. - 1963. - T. 1 . - doi : 10.1007/BF02759702 .
Frederic Maffray. Ytimet täydellisissä viivakaavioissa // Journal of Combinatorial Theory . - 1992. - T. 55 , no. 1 . - S. 1-8 . - doi : 10.1016/0095-8956(92)90028-V .
Francesco Barioli. Täysin positiiviset matriisit kirja-graafilla // Lineaarinen algebra ja sen sovellukset. - 1998. - T. 277 . - doi : 10.1016/S0024-3795(97)10070-2 .
Erdős P. Rademacher-Turánin lauseesta // Illinois Journal of Mathematics. - 1962. - T. 6 .