Descomposiciones de grafos regulares

• Autores: Amauri Gutiérrez Hernández
• Directores de la Tesis: Anna Lladó Sánchez (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2000
• Idioma: español
• Tribunal Calificador de la Tesis: Miguel Ángel Fiol Mora (presid.) , Francisco Aguiló Gost (secret.) , Ibrahim Cahit (voc.) , Alberto Márquez Pérez (voc.) , Marc Noy Serrano (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • El trabajo desarrollado en la presente tesis trata tres problemas clasicos de la Teoria de Grafos en el contexto de grafos El Capitulo 2, está dedicado al estudio de las descomposiciones minimales de grafos regulares en árboles, Una descomposición en árboles de un grafo G, es una familia de árboles arista-disjuntos cuyos conjuntos de aristas recubren el conjunto de aristas de G. El numero minimo de arboles en una descomposición de este tipo se denota por t(G). Demostramos, haciendo uso de las conectividades de ordenes superiores, que t(G)=a(G) para todo grafo regular de $n$ vertices y grado d<=n/2 siendo a(G)I a arbolicidad del grafo. Damos ademas, una familia de grafos que muestran que esta cota es la mejor posible. El Capitulo concluye con el estudio de descomposiciones de grafos de Cayley en bosques isomorfos.

    Demostramos que si S es un conjunto generador quasiminimal de un grupo H y F s un bosque orienado con cardinal de S aristas, entonces el grafo de Cayley Cay(H,S) admite una F--descomposicion. Cuestiones particulares en el caso del hipercubo n-dimensional Q-n. Tambien son analizadas.

    En el Capitulo 3 tratamos el problema de los empaquetamientos de grafos regulares. Un conocido teorema R.Wilson establece que, para todo grafo G, el grafo completo K-n es G-descomponible siempre que n sea suficientemente grande en relacion al orden de G y se satisfagan ciertas condiciones naturales de divisibilidad. En esta Capitulo se plantea el problema de determinar, dado un grafo regular G, el menor entero N-0(G) para que el existe un grafo conexo regular G-descomponible distinto de G. Para el análisis de este problema, se introduce un nuevo parametro, el numero de empaquetamiento de un grafo. Se utiliza dicho parametro, para obtener cotas generales de N-0(G), resultados sobre grafos autoempaquetables, es decir, aquellos para los que N-0(G) es el orden de g, y se dan cotas ajustadas para los valores de N-0(G) para grafos regulares densos