Inmersiones de grafos en pseudosuperficiesGrafos prohibidos, invariantes y algoritmos

Abstract

En esta memoria se estudia la finitud e infinitud de los conjuntos de grafos prohibidos para algunas familias de pseudosuperficies, dándose dichos conjuntos de manera explícita en algunos casos en los que es finito, y subconjuntos infinitos en algunos casos en los que es infinito. Concretamente, se prueba que si la pseudosuperficie está formada por dos células que son superficies y estas están unidas por al menos dos puntos, la pseudosuperficie tiene una cantidad infinita de grafos prohibidos. Al igual que los conceptos de género y género no orientable surgen de inmersiones en familias de superficies, a partir de inmersiones en familias de pseudosuperficies aparecen dos nuevos invariantes, llamados s y j, de los que se hayan sus valores para las dos familias de grafos principales: los grafos completos y los grafos bipartidos completos. Se prueba también que el problema tiene como entrada un grafo y un natural y que determina si s del grafo es menor o igual que el natural es NP-completo. También se observa la relación entre los valores de ambos invariantes en cada grafo y se compara con otros invariantes clásicos de la teoría de grafos topológicos como el género, el género no orientable, el cruzamiento, la escisión, el grosor, etc., los cuales, al igual que s y j, dan una medida de la complejidad del grafo. Aunque ya eran conocidas las psuedosuperficies cuyo conjunto de grafos que no admiten una inmersión en ella no eran caracterizables por menores, no se conocen en general, ejemplos de grafos que admitan una inmersión en ellas, pero que algún menor suyo no la admita. En esta memoria se presentan ejemplos para pseudosuperficies formadas por una célula. También se exponen varios algoritmos. Era conocida la existencia de algoritmos. Era conocida la existencia de algoritmos polinomiales que determinan si un grafo admite una inmersión en una superficie o psedosuperficie concreta con una cantidad finita de grafos