Gráfico cuártico

En el campo matemático de la teoría de grafos , un grafo cuártico es un grafo donde todos los vértices tienen grado 4. En otras palabras, un grafo cuártico es un grafo 4-regular . ^{[ 1 ]}

Varias gráficas muy conocidas son cuárticas. Entre ellas se incluyen:

• El grafo completo K ₅ , un grafo cuártico con 5 vértices, el grafo cuártico más pequeño posible.
• El grafo de Chvátal , otro grafo cuártico con 12 vértices, el grafo cuártico más pequeño que no tiene triángulos y no puede colorearse con tres colores. ^{[ 2 ]}
• El grafo de Folkman , un grafo cuártico con 20 vértices, es el grafo semisimétrico más pequeño . ^{[ 3 ]}
• El grafo de Meredith , un grafo cuártico con 70 vértices que es 4-conexo pero no tiene ciclo hamiltoniano , refuta una conjetura de Crispin Nash-Williams . ^{[ 4 ]}

Todo grafo medial es un grafo plano cuártico , y todo grafo plano cuártico es el grafo medial de un par de grafos planos duales o multigrafos. ^{[ 5 ]} Los diagramas de nudos y los diagramas de enlaces también son multigrafos planos cuárticos , en los que los vértices representan los cruces del diagrama y están marcados con información adicional sobre cuál de las dos ramas del nudo cruza la otra rama en ese punto. ^{[ 6 ]} El grafo de líneas de cualquier grafo cúbico es cuártico; el grafo cuboctaédrico es un ejemplo, como el grafo de líneas de un grafo cúbico .

Debido a que el grado de cada vértice en un grafo cuártico es par, todo grafo cuártico conexo tiene un recorrido de Euler . Y al igual que con los grafos bipartitos regulares en general, todo grafo cuártico bipartito tiene un emparejamiento perfecto . En este caso, es posible un algoritmo mucho más simple y rápido para encontrar dicho emparejamiento que para los grafos irregulares: al seleccionar una arista sí y otra no de un recorrido de Euler, se puede encontrar un 2-factor , que en este caso debe ser una colección de ciclos, cada uno de longitud par, donde cada vértice del grafo aparece en exactamente un ciclo. Al seleccionar nuevamente una arista sí y otra no en estos ciclos, se obtiene un emparejamiento perfecto en tiempo lineal . El mismo método también se puede usar para colorear las aristas del grafo con cuatro colores en tiempo lineal. ^{[ 7 ]}

Los grafos cuárticos tienen un número par de descomposiciones hamiltonianas . ^{[ 8 ]}

Es una conjetura abierta si todos los grafos hamiltonianos cuárticos tienen un número par de circuitos hamiltonianos o más de uno. Se sabe que la respuesta es falsa para los multigrafos cuárticos . ^{[ 9 ]}

• Gráfico cúbico

• Weisstein, Eric W. "Grafo cuártico" . MathWorld .