Libro (teoría de grafos)

Un libro triangular

En 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 denominarse libro cuadrilátero , consta de p cuadriláteros que comparten un borde común (conocido como "lomo" o "base" del libro). Es decir, es un producto cartesiano de una estrella y una única arista. ^{[1] [2]} El gráfico de libro de 7 páginas de este tipo proporciona un ejemplo de un gráfico sin etiquetado armonioso . ^[2]

Un segundo tipo, que podría denominarse libro triangular , es el gráfico tripartito completo K _{1,1, p} . Es un gráfico formado por triángulos que comparten un borde 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 (en honor a los thagomizers , las colas puntiagudas de los dinosaurios estegosaurios , debido a su apariencia puntiaguda en ciertos dibujos) y sus matroides gráficas han sido llamadas matroides thagomizer. ^[5] Los libros triangulares forman uno de los componentes clave de los gráficos lineales perfectos . ^[6] ${\displaystyle p}$ ${\displaystyle K_{e}(2,p)}$

El término "libro-gráfico" se ha empleado para otros usos. Barioli ^[7] lo usó para referirse a un gráfico compuesto por un número de 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) contenido en . ${\displaystyle G}$ ${\displaystyle bk(G)}$ ${\displaystyle G}$

Teoremas en libros

Denote el número de Ramsey de dos libros triangulares por Este es el número más pequeño tal que para cada gráfico de vértice, el gráfico en sí contiene un subgrafo o su gráfico complemento contiene un subgrafo. ${\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 . Entonces cada gráfico en 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 libros". MundoMatemático .
2. Gallian, Joseph A. (1998). "Un estudio dinámico del etiquetado de gráficos". Revista Electrónica de Combinatoria . 5 : Encuesta dinámica 6. SEÑOR  1668059.
3. Lingsheng Shi; Canción de Zhipeng (2007). "Límites superiores del radio espectral de gráficos sin libros y/o sin K2,l". Álgebra lineal y sus aplicaciones . 420 (2–3): 526–9. doi : 10.1016/j.laa.2006.08.007 .
4. Erdős, Paul (1963). "Sobre la estructura de gráficos lineales". Revista Israelí de Matemáticas . 1 (3): 156–160. doi : 10.1007/BF02759702 .
5. Gedeon, Katie R. (2017). "Polinomios de Kazhdan-Lusztig de matroides tagomizadoras". Revista Electrónica de Combinatoria . 24 (3). Documento 3.12. arXiv : 1610.05349 . doi :10.37236/6567. SEÑOR  3691529. S2CID  23424650.; Xie, Mateo HY; Zhang, Philip B. (2019). "Polinomios equivariantes de Kazhdan-Lusztig de matroides tagomizadoras". Actas de la Sociedad Matemática Estadounidense . 147 (11): 4687–4695. arXiv : 1902.01241 . doi : 10.1090/proc/14608 . SEÑOR  4011505.; Pie orgulloso, Nicolás; Ramos, Eric (2019). "Invariantes funcionales de árboles y sus conos". Selecta Matemática . Series nuevas. 25 (4). Documento 62. arXiv : 1903.10592 . doi :10.1007/s00029-019-0509-4. SEÑOR  4021848. S2CID  85517485.
6. Maffray, Frédéric (1992). "Núcleos en gráficos lineales 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 libro-gráfico". Álgebra lineal y sus aplicaciones . 277 (1–3): 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 .