Bok (grafteori) - Book (graph theory)

En triangulär bok

I grafteori kan en bokgraf (ofta skriven  ) vara vilken som helst av flera typer av diagram som bildas av flera cykler som delar en kant. ${\ displaystyle B_ {p}}$

Variationer

En typ, som kan kallas en fyrkantig bok , består av p fyrkantiga delar som delar en gemensam kant (känd som bokens "ryggrad" eller "bas"). Det är, det är en kartesisk produkt av en stjärna och en enda kant. Den 7-sidiga bokgrafen av denna typ ger ett exempel på en graf utan harmonisk märkning .

En andra typ, som kan kallas en triangulär bok , är det kompletta trepartsdiagrammet K _{1,1, s} . Det är en graf som består av trianglar som delar en gemensam kant. En bok av denna typ är en delad graf . Denna graf har också kallats en eller en thagomizer-graf (efter thagomizers , de spetsiga svansarna av Stegosaurus- dinosaurier, på grund av deras spetsiga utseende på vissa ritningar) och deras grafiska matroider har kallats thagomizer-matroider. Triangulära böcker utgör en av de viktigaste byggstenarna för perfekta grafer . ${\ displaystyle p}$ ${\ displaystyle K_ {e} (2, p)}$

Termen "bokgraf" har använts för andra användningsområden. Barioli använde det för att betyda en graf som består av ett antal godtyckliga underbilder med två hörnpunkter gemensamt. (Barioli skrev inte för sin bokgraf.) ${\ displaystyle B_ {p}}$

Inom större diagram

Med en graf kan man skriva för den största boken (av det slag som övervägs) som finns i . ${\ displaystyle G}$${\ displaystyle bk (G)}$${\ displaystyle G}$

Satser om böcker

Beteckna Ramsey antal av två triangulära böcker av detta är det minsta antalet sådan att för varje -vertex graf, antingen själva grafen innehåller som en subgraf eller dess komplementgraf innehåller som en subgraf. ${\ displaystyle r (B_ {p}, \ B_ {q}).}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle B_ {p}}$${\ displaystyle B_ {q}}$

• Om , då .${\ displaystyle 1 \ leq p \ leq q}$${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3}$
• Det finns en konstant sådan att när som helst .${\ displaystyle c = o (1)}$${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3}$${\ displaystyle q \ geq cp}$
• Om och är stort, ges Ramsey-numret av .${\ displaystyle p \ leq q / 6 + o (q)}$${\ displaystyle q}$${\ displaystyle 2q + 3}$
• Låt vara en konstant, och . Sedan innehåller varje graf på hörn och kanter ett (triangulärt) .${\ displaystyle C}$${\ displaystyle k = Cn}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle B_ {k}}$

Referenser