Resumen - Una caracterización constructiva de los gráficos uniformemente 4-conectados

Una caracterización constructiva de los gráficos uniformemente 4-conectados

2025-07-10 11:30:36

{"Xiang Chen","Shuai Kou","Chengfu Qin","Liqiong Xu","Weihua Yang"}

{math.CO}

El documento presenta una caracterización constructiva de grafos uniformemente 4-conectados. Estos grafos se caracterizan por que el número máximo de caminos internamente disjuntos entre cualquier par de vértices es exactamente 4. Los autores proporcionan un método para construir tales grafos mediante operaciones de grafo aplicadas a conjuntos adecuados de vértices y aristas. La idea principal es que cualquier grafo uniformemente 4-conectado se puede obtener de dos grafos básicos, C2_5 o C2_6, a través de una serie de operaciones ∆_1 o ∆_2. Estas operaciones involucran la adición de nuevos vértices y aristas manteniendo la uniforme 4-conectividad. El documento comienza introduciendo algunas definiciones y lemas básicos, como los conceptos de caminos de división de circuitos cuasi 3-circulares, operaciones ∆_1 y ∆_2, y la cuasi 4-compatibilidad. Luego prueba varios lemas, como la existencia de aristas removibles en grafos 4-conectados y el método de construcción para grafos k-conectados. El resultado principal del documento se presenta en el Teorema 9. Este afirma que un grafo G es uniformemente 4-conectado si y solo si es isomorfo a C2_5 o C2_6, o puede ser construido aplicando operaciones ∆_1 o ∆_2 a un grafo uniformemente 4-conectado más pequeño. Para probar este resultado, los autores primero muestran que cualquier grafo uniformemente 4-conectado excepto C2_5 y C2_6 contiene una arista removible. Luego consideran varios casos dependiendo del grado de los extremos de esta arista removible. En cada caso, muestran que G puede ser construido aplicando operaciones ∆_1 o ∆_2 a un grafo uniformemente 4-conectado más pequeño. El documento concluye ilustrando cómo resolver el problema de construir una secuencia de grafos 4-conectados que satisfagan ciertas condiciones, utilizando los conceptos y resultados presentados anteriormente. En resumen, el documento proporciona un método constructivo para construir grafos uniformemente 4-conectados y los caracteriza utilizando operaciones de grafo y cuasi 4-compatibilidad. Los resultados presentados en el documento pueden ser útiles para estudiar las propiedades de los grafos uniformemente conectados y sus aplicaciones en diversos campos.