Libro (teoría de grafos)

No confundir con incrustación de libros .

Un libro triangular

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

Variaciones

Un tipo, que puede llamarse libro cuadrilátero , consta de p cuadriláteros que comparten un borde común (conocido como el "lomo" o "base" del libro). Es decir, es un producto cartesiano de una estrella y un solo borde. ^{[1] [2]} El gráfico de libro de 7 páginas de este tipo proporciona un ejemplo de un gráfico sin un etiquetado armonioso . ^[2]

Un segundo tipo, que podría llamarse libro triangular , es el gráfico tripartito completo K _{1,1, p} . Es un gráfico que consta de triángulos que comparten una arista común. ^[3] Un libro de este tipo es un gráfico dividido . Este gráfico también ha sido llamado ^[4] o gráfico thagomizer (después de thagomizers , las colas puntiagudas de los dinosaurios Stegosaurus , debido a su apariencia puntiaguda en ciertos dibujos) y sus matroides gráficos se han llamado matroids thagomizer. ^{[5] Los} libros triangulares forman uno de los bloques de construcción clave de${\displaystyle p}$ ${\displaystyle K_{e}(2,p)}$gráficos de líneas perfectas . ^[6]

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

Dentro de gráficos más grandes

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

Teoremas sobre libros

Denote el número de Ramsey de dos libros triangulares por Este es el número más pequeño de modo que para cada gráfico de vértice, el gráfico en sí contiene como un subgráfico o su gráfico complementario contiene como un subgráfico.${\displaystyle r(B_{p},\ B_{q}).}$${\displaystyle r}$${\displaystyle r}$${\displaystyle B_{p}}$${\displaystyle B_{q}}$

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

Referencias

1. Weisstein, Eric W. "Gráfico de libro" . MathWorld .
2. Gallian, Joseph A. (1998). "Una encuesta dinámica de etiquetado de gráficos" . Revista electrónica de combinatoria . 5 : Encuesta dinámica 6. MR 1668059 . 
3. Lingsheng Shi; Canción de Zhipeng (2007). "Límites superiores en el radio espectral de gráficos libres de libros y / o K 2, l -free gráficos" . Álgebra lineal y sus aplicaciones . 420 : 526–9. doi : 10.1016 / j.laa.2006.08.007 .
4. Erdős, Paul (1963). "Sobre la estructura de los gráficos lineales". Revista de Matemáticas de Israel . 1 : 156–160. doi : 10.1007 / BF02759702 .
5. Gedeon, Katie R. (2017). "Polinomios de Kazhdan-Lusztig de matroides thagomizer". Revista electrónica de combinatoria . 24 (3). Documento 3.12. Señor 3691529 . ; Xie, Matthew HY; Zhang, Philip B. (2019). "Polinomios equivariantes de Kazhdan-Lusztig de matroides thagomizer" . Actas de la American Mathematical Society . 147 (11): 4687–4695. doi : 10.1090 / proc / 14608 . Señor 4011505 . ; Proudfoot, Nicholas; Ramos, Eric (2019). "Invariantes functoriales de árboles y sus conos". Selecta Mathematica . Series nuevas. 25 (4). Documento 62. arXiv : 1903.10592 . doi : 10.1007 / s00029-019-0509-4 . Señor 4021848 . 
6. Maffray, Frédéric (1992). "Núcleos en gráficos de líneas perfectos". Revista de teoría combinatoria . Serie B. 55 (1): 1–8. doi : 10.1016 / 0095-8956 (92) 90028-V . Señor 1159851 . .
7. Barioli, Francesco (1998). "Matrices completamente positivas con un libro-gráfico" . Álgebra lineal y sus aplicaciones . 277 : 11–31. doi : 10.1016 / S0024-3795 (97) 10070-2 .
8. Rousseau, CC ; Sheehan, J. (1978). "Sobre los números de Ramsey para libros". Revista de teoría de grafos . 2 (1): 77–87. doi : 10.1002 / jgt.3190020110 . Señor 0486186 . 
9. Erdős, P. (1962). "Sobre un teorema de Rademacher-Turán" . Revista de Matemáticas de Illinois . 6 : 122–7. doi : 10.1215 / ijm / 1255631811 .