Estudio del número de Ramsey R(3,10): análisis de gráficas de orden 40

Resumen

El número de Ramsey R(k,l) es el entero más pequeño n tal que no hay (k,l,n,e)-grafo, donde un (k,l,n,e)-grafo denota un grafo G con n vértices y e aristas y con C(G)<k e I(G)<l, en que C(G) denota el clic más grande en G y I(G) denota el conjunto independiente más grande en G. La teoría de grafos dio origen a una extensa investigación, pues por más simple que sea la definición, calcular los números de Ramsey es una tarea ardua y que pocos conocen. Exoo (1989), Goedgebeur y Radziszowski (2013) mostraron que 40 <= R(3,10) <= 42. Así, en este artículo expondremos proposiciones que serán de utilidad en el cálculo de este número de Ramsey. Basado en las ideas de Grinstead y Roberts (1982) y Cariolaro (2007), se mostrarán las propriedades e caracteristicas para un grafo G bicolor de orden 40, tal que G está libre de triángulos, esto es, C(G)<3, y no tiene un conjunto independiente de orden 10, es decir, I(G)<10. Mostraremos, por ejemplo, que dado G = (V,E) un grafo de orden 40 y con C(G) < 3 y I(G) < 10, entonces, para todo vértice v en V, tenemos que 4 <= deg(v) <= 9. Finalmente, destacamos que los resultados inéditos obtenidos por los autores, en un proyecto de investigación desarrollado en IFRS, Campus Alvorada, se encuentran en la Sección 4.