Las gráficas planas cúbicas tienen $2^m-1$ Hamilton Cycles, contradiciendo a Bosak...

Question

Me fijé en la diferencia simétrica del ciclo de Hamilton (HC) en los grafos cúbicos planos y encontré que, junto con el grafo vacío, construyen un subgrupo del grupo abeliano $\Omega$ de las diferencias simétricas de los ciclos. Esto se ilustra fácilmente con las HC del gráfico de Frucht:

¡Comprueba tú mismo que la diferencia simétrica de cualquier par da la tercera HC! (También es interesante observar que el conjunto de cortes de pares construye un $3$ -coloración de aristas del gráfico)

Ahora el espacio de los ciclos es abarcado por las caras $f_k\in F$ de $G$ y es una especie de conjunto de potencias de las caras, ya que en la suma simétrica total, se activa/desactiva una determinada cara. Esto da como resultado un $F$ espacio vectorial dimensional sobre $\mathbb Z_2$ que tiene $2^F$ que son los elementos del grupo de $\Omega$ .

Ahora me pregunto si es cierto en general, que el número de HCs más $1$ divide $2^F$ ya que el subgrupo es normal, incluso central. Como se muestra en una referencia aquí siempre tendremos tres HC en los gráficos cúbicos.

Bien, pero esto se opone a lo que leí en otro lugar (tratando de dar una referencia) de que los gráficos bicúbicos siempre tienen cuatro HC. ¿O estos cuatro no construyen un único subgrupo, sino un conjunto de subgrupos?

¿Qué sucede en el caso de las bicúbicas y es cierto para las cúbicas que siempre tienen $2^m-1$ ¿HCs?

Estoy confundido, ya que encontré esta cita "Todo grafo bipartito cúbico tiene un número par de ciclos Hamilton ." de J. Bosak, Hamiltonian lines in cubic graphs,Theory of Graphs, International Symposium, Rome, July 1966 , Gordon & Breach, New York, (1967), 35-46. por ejemplo aquí ...contradiciendo mi suposición...

Answer 1

Dejemos que $K$ sea el mencionado grupo de ciclos hamiltonianos. Tiene un tamaño $H+1$ , donde $H$ es el número de ciclos hamiltonianos.

Dejemos que $J$ sea el grupo de $S\subset \mathscr{P}(\text{faces})$ bajo diferencia simétrica.

Voy a formalizar tu idea sobre cada ciclo hamiltoniano $h$ que se envía a un conjunto $f(h)$ de caras monomórficamente por $f:J \to K$ Entonces, observando que $\vert\text{im}f\vert \mid \vert K\vert=2^n$ hemos terminado.

Está razonablemente claro que un ciclo es hamltoniano si su interior es un $2$ -conjunto conexo de vértices cuya frontera contiene todos los vértices (llamamos al conjunto de estos $J'$ ). Por tanto, existe una biyección que envía ciclos $h$ a $j_h\in J' \subset J$ . Definir $f$ usando esto. Es obvio que $f$ es un homomorfismo.

Lo único que queda por comprobar es que, si $h,g$ son ciclos hamiltonianos, $f(hg)$ es el elemento esperado en $J$ : $f(h) \Delta f(g)$ . De hecho, considere $f(h) \Delta f(g)$ que corresponde a algún ciclo hamiltoniano por el párrafo anterior.

Para demostrar que esto es $f(gh)$ , mira localmente en cada vértice $v$ . Para simplificar $h \ne g$ en este vértice. Entonces dos de las tres aristas de $v$ son atravesados por $g$ y $h$ , no los dos son iguales para $g$ y $h$ . Tomando la diferencia simétrica se obtienen dos nuevas aristas. Con un par de saltos de caja es obvio que estas dos nuevas aristas son el límite de $f(g)\Delta f(h)$ cerca de $v$ .

Si $h,g$ estar de acuerdo con $v$ es trivial.

TL;DR: El mapa que lleva una HC al conjunto de caras que encierra es monomorfo, luego mira las cardinalidades.

Answer 2

Morgan tenía razón: no he comprobado los contraejemplos simples. Aquí hay uno. Un gráfico puede contener 3 cuadrados adyacentes, lo que da lugar a dos tipos de ciclos hamiltonianos y la diferencia simétrica no es otro HC, sino un ciclo separado.