Kniha (teorie grafů)

Kniha (často psaná ) může být jakýkoli graf nějakého druhu, který je tvořen cykly, které sdílejí hranu. $B_{p}$

Variace

Jeden druh, který lze nazvat knihou čtyřúhelníků , se skládá z p čtyřúhelníků , které sdílejí hranu (známou jako „hřbet“ nebo „základna“ knihy). To znamená, že jde o přímý součin hvězdy a jediné hrany [1] [2] . 7stránková kniha tohoto typu uvádí příklad grafu bez harmonického značení [2] .

Druhým druhem, který lze nazvat knihou trojúhelníků nebo trojúhelníkovou knihou , je úplný bipartitní graf K 1,1, p . Jedná se o graf skládající se z trojúhelníků se společnou hranou [3] . Kniha tohoto typu je rozdělený graf . Tento graf lze také nazvat [4] . Trojúhelníkové knihy tvoří jeden z klíčových stavebních kamenů hraně dokonalých grafů [5] . $p$ $K_{e}(2,p)$

Termín "graf-kniha" byl použit pro jiné účely. Barioli [6] jej tedy použil pro grafy složené z libovolných podgrafů, které mají dva společné vrcholy. (Barioli nepoužil notaci pro tyto knižní grafy.) $B_{p}$

Uvnitř velkých grafů

Daný graf , lze psát pro největší knihu (dotyčného typu) obsaženou v . $G$ $bk(G)$ $G$

Věty o knihách

Označme Ramseyovo číslo dvou trojúhelníkových knih , což je nejmenší číslo takové, že pro ostrý graf s vrcholy buď graf samotný obsahuje jako podgraf, nebo jeho doplněk obsahuje jako podgraf. $r(B_{p},\ B_{q}).$ $r$ $r$ $B_{p}$ ${\displaystyle B_{q))$

Pokud , tak (dokázáno Rousseauem a Shihanem). $1\leqslant p\leqslant q$ $r(B_{p},\ B_{q})=2q+3$
Existuje konstanta taková, že když . $c=o(1)$ $r(B_{p},\ B_{q})=2q+3$ $q\geqslant cp$
Jestliže a je dostatečně velké, Ramseyovo číslo je dáno . $p\leqslant q/6+o(q)$ $q$ $2q+3$
Nechť být konstantní a . Pak libovolný graf s vrcholy a hranami obsahuje (knihu trojúhelníků) [7] . $C$ $k=Cn$ $n$ $m$ $B_{k}$

Poznámky

↑ Weisstein, Eric W. Book Graph na webu Wolfram MathWorld .
↑ 1 2 Gallian, 1998 , s. Dynamický průzkum 6.
↑ Shi, Song, 2007 , str. 526-529.
↑ Erdős, 1963 , s. 156–160.
↑ Maffray, 1992 , str. 1–8.
↑ Barioli, 1998 , s. 11–31.
↑ Erdős, 1962 , str. 122-127.

Literatura

Josef Gallian. Dynamický přehled označování grafů // Electronic Journal of Combinatorics . - 1998. - T. 5 .
Lingsheng Shi, Zhipeng Song. Horní hranice spektrálního poloměru grafů bez knih a/nebo bez K 2,l // Lineární algebra a její aplikace. - 2007. - T. 420 . - doi : 10.1016/j.laa.2006.08.007 .
Paul Erds . O struktuře lineárních grafů // Israel Journal of Mathematics. - 1963. - T. 1 . - doi : 10.1007/BF02759702 .
Frederic Maffray. Jádra v dokonalých spojnicových grafech // Journal of Combinatorial Theory . - 1992. - T. 55 , no. 1 . — S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V .
Francesco Barioli. Zcela pozitivní matice s knižním grafem // Lineární algebra a její aplikace. - 1998. - T. 277 . - doi : 10.1016/S0024-3795(97)10070-2 .
Erdős P. O teorému Rademacher-Turán // Illinois Journal of Mathematics. - 1962. - T. 6 .