Libro (teoría de grafos)

En teoría de grafos , un grafo de libro (a menudo escrito)${\displaystyle B_{p}}$ ) puede ser cualquiera de varios tipos de grafos formados por múltiples ciclos que comparten una arista.

Un tipo, que puede denominarse libro cuadrilátero , consta de p cuadriláteros que comparten una arista común (conocida como la "espina" o "base" del libro). Es decir, es un producto cartesiano de una estrella y una sola arista. ^{[ 1 ] [ 2 ]} El grafo de libro de 7 páginas de este tipo proporciona un ejemplo de un grafo sin etiquetado armónico . ^{[ 2 ]}

Un segundo tipo, que podría llamarse libro triangular , es el grafo tripartito completo K _{1,1, p} . Es un grafo que consta de${\displaystyle p}$triángulos que comparten una arista común. ^{[ 3 ]} Un libro de este tipo es un grafo dividido . Este grafo también ha sido llamado${\displaystyle K_{e}(2,p)}$^{[ 4 ]} o ungrafo thagomizer(en honor alos thagomizers, las colas puntiagudas deestegosaurios, debido a su apariencia puntiaguda en ciertos dibujos) y susmatroides gráficosse han denominado matroides thagomizer. ^{[ 5 ]} Los libros triangulares forman uno de los bloques de construcción clave delos grafos perfectos de línea. ^{[ 6 ]}

El término "grafo-libro" se ha empleado para otros usos. Barioli ^{[ 7 ]} lo usó para referirse a un grafo compuesto por varios subgrafos arbitrarios que tienen dos vértices en común. (Barioli no escribió${\displaystyle B_{p}}$(para su libro-gráfico.)

Dado un gráfico${\displaystyle G}$, uno puede escribir${\displaystyle bk(G)}$para el libro más grande (del tipo que se está considerando) contenido en${\displaystyle G}$.

Denotemos el número de Ramsey de dos libros triangulares por${\displaystyle r(B_{p},\ B_{q}).}$Este es el número más pequeño${\displaystyle r}$de tal manera que para cada${\displaystyle r}$-grafo de vértices, ya sea que el grafo en sí contenga${\displaystyle B_{p}}$como un subgrafo, o su grafo complemento contiene${\displaystyle B_{q}}$como subgrafo.

• Si${\displaystyle 1\leq q}$, entonces${\displaystyle r(B_{1},\ B_{q})=2q+3}$. ^{[ 8 ]}
• Existe una constante${\displaystyle c=o(1)}$de tal manera que${\displaystyle r(B_{p},\ B_{q})=2q+3}$cuando sea${\displaystyle q\geq cp}$.
• Si${\displaystyle p\leq q/6+o(q)}$, y${\displaystyle q}$es grande, el número de Ramsey viene dado por${\displaystyle 2q+3}$.
• Dejar${\displaystyle C}$ser una constante, y${\displaystyle k=Cn}$. Luego cada gráfico en${\displaystyle n}$vértices y${\displaystyle m}$Los bordes contienen un (triangular)${\displaystyle B_{k}}$. ^{[ 9 ]}