¿Se representan todos los gráficos cuárticos como nudos planos?

Question

Estoy pensando en nudos planos y cómo pueden representar un gráfico. La mayoría de los nudos planos tienen un cordón siguiendo un patrón de sobre-paso conectándose a sí mismo. Aquí tienes un nudo triplicado:

Este tipo de nudos deben ser cuárticos ya que todos los grafos con circuitos eulerianos existen en grafos con nodos pares conectados. Bueno, eso y el hecho de que cualquier par de cuerdas cruzadas da cuatro y solo cuatro bordes.

Sea $G$ un grafo conectado, plano, cuártico, formado por bordes $E$ y nodos $V.

Sea $e_1, \dots, e_m$ un circuito euleriano de bordes y $n_1, \dots, n_{m-1}$ los nodos correspondientes que conectan los bordes consecutivos. Es decir, $n_i$ conecta los bordes $e_i$ y $e_{i+1}$. Además, que haya un nodo $n_m$ que conecta $e_m$ y $e_1$.

Mi pregunta es: ¿Existe un mapa $f:V \to \{0, 1\}$ y un circuito euleriano como se especificó anteriormente, tal que $f(n_i)$ alterne entre $0$ y $1$? ¿Cuáles son las condiciones necesarias y suficientes para que un grafo cuártico conectado cumpla lo anterior?

Answer 1

Sea $G$ un grafo cuártico, plano y conexo y supongamos que encontramos un mapa $f$ y un circuito euleriano como se describe en la pregunta.

Dado que el grado de cada vértice es cuatro, entonces en el circuito euleriano, cada vértice $v$ debe incluirse exactamente dos veces en la secuencia de nodos correspondientes al circuito euleriano, digamos en los índices $i$ y $j$. Observa que si la paridad de $i$ y $j$ difiere, entonces nuestro mapa ya no tiene su propiedad alternante (ya que $f(n_i) = f(n_j)$ y la diferencia entre $i$ y $j$ es impar). Por lo tanto, debe ser el caso que la paridad de $i$ y $j$ es la misma y podemos asignar esta paridad al vértice $v$. Si la paridad es par, diremos que $v$ está indexado de manera par, si es impar, diremos que $v$ está indexado de manera impar.

Esto divide los vértices de $G$ en vértices indexados de manera par e impar. Observa que debido a la construcción del circuito euleriano, si tenemos un número par de vértices, entonces los vértices indexados de manera par solo están conectados a vértices indexados de manera impar y los vértices indexados de manera impar solo están conectados a vértices indexados de manera par y por lo tanto, $G$ es de hecho bipartito donde cada partición contiene la misma cantidad de vértices (es decir, $G$ es un grafo bipartito balanceado).

Si el número de vértices es impar, entonces tenemos algo cercano a un grafo bipartito con una arista agregada dentro de una de las particiones. Supondría que también quieres que la propiedad alternante de $f$ también "retroceda" en cierto sentido, es decir, $f(n_m) \neq f(n_1)$. Esto solo puede ocurrir si el número de vértices es par, por lo que podemos descartar el caso de un número impar de vértices si queremos que la propiedad alternante "retroceda".

No es demasiado exigente computacionalmente determinar si un grafo es bipartito y encontrar las dos particiones. Si estamos tratando de encontrar un circuito euleriano y un mapeo $f$ para $G$, simplemente podemos probar la bipartitividad y encontrar las particiones. Si el grafo no es bipartito, sabemos que no existe ningún circuito y mapeo. Si $G$ es bipartito, es suficiente elegir cualquier circuito euleriano y asignar los vértices en una partición como $0$ y los vértices en la otra partición como $1$.