Könyv (gráfelmélet)

A könyv (gyakran írva ) lehet bármilyen gráf, amelyet olyan ciklusok alkotnak, amelyeknek egy élük van. $B_{p}$

Változatok

Az egyik fajta, amelyet quadok könyvének nevezhetünk , p négyszögből áll, amelyeknek közös élük van (a könyv "gerince" vagy "alapja" néven ismert). Vagyis egy csillag és egyetlen él közvetlen szorzata [1] [2] . Egy ilyen típusú 7 oldalas könyv példát ad harmonikus jelölés nélküli gráfra [2] .

A második típus, amelyet háromszögkönyvnek vagy háromszögkönyvnek nevezhetünk , a teljes kétrészes gráf K 1,1, p . Ez egy közös élű háromszögekből álló gráf [3] . Az ilyen típusú könyv egy osztott gráf . Ezt a grafikont [4] -nek is nevezhetjük . A háromszögkönyvek az él-perfect gráfok egyik kulcsfontosságú építőkövét alkotják [5] . $p$ $K_{e}(2,p)$

A „grafikonkönyv” kifejezést más célokra is használták. Így Barioli [6] tetszőleges részgráfokból álló gráfokhoz használta, amelyeknek két közös csúcsa van. (Barioli nem használta a jelölést ezekhez a könyvgrafikonokhoz.) $B_{p}$

A nagy grafikonok belsejében

Adott egy gráf , akkor a legnagyobb (a kérdéses típusú) könyvre írható . $G$ $bk(G)$ $G$

Tételek könyvekről

Jelöljük két háromszögkönyv Ramsey-számát, amely a legkisebb szám , amelynél egy heves csúcsú gráfnál vagy maga a gráf részgráfként, vagy a komplementere részgráfként szerepel . $r(B_{p},\ B_{q}).$ $r$ $r$ $B_{p}$ ${\displaystyle B_{q))$

Ha , akkor (Rousseau és Shihan bizonyítja). $1\leqslant p\leqslant q$ $r(B_{p},\ B_{q})=2q+3$
Van egy olyan állandó , hogy amikor . $c=o(1)$ $r(B_{p},\ B_{q})=2q+3$ $q\geqslant cp$
Ha és elég nagy, akkor a Ramsey-számot a . $p\leqslant q/6+o(q)$ $q$ $2q+3$
Legyen állandó, és . Ekkor bármely csúcsokkal és élekkel rendelkező gráf tartalmaz (egy háromszögkönyvet) [7] . $C$ $k=Cn$ $n$ $m$ $B_{k}$

Jegyzetek

↑ Weisstein, Eric W. Book Graph a Wolfram MathWorld webhelyen .
↑ 1 2 Gallian, 1998 , p. Dinamikus felmérés 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.

Irodalom

Joseph Gallian. A grafikoncímkézés dinamikus felmérése // Electronic Journal of Combinatorics . - 1998. - T. 5 .
Lingsheng Shi, Zhipeng Song. Könyvmentes és/vagy K 2,l -mentes gráfok spektrális sugarának felső határa // Lineáris algebra és alkalmazásai. - 2007. - T. 420 . - doi : 10.1016/j.laa.2006.08.007 .
Erds Pál . A lineáris gráfok szerkezetéről // Israel Journal of Mathematics. - 1963. - T. 1 . - doi : 10.1007/BF02759702 .
Frederic Maffray. Kernelek tökéletes vonalgráfokban // Journal of Combinatorial Theory . - 1992. - T. 55 , sz. 1 . – S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V .
Francesco Barioli. Teljesen pozitív mátrixok könyvgráffal // Lineáris algebra és alkalmazásai. - 1998. - T. 277 . - doi : 10.1016/S0024-3795(97)10070-2 .
Erdős P. Rademacher-Turán tételéről // Illinois Journal of Mathematics. - 1962. - T. 6 .