Demostrar que si $G$ y $H$ es hamiltoniano entonces $G \times H$ es hamiltoniano

Question

Demostrar que si $G$ y $H$ es hamiltoniano entonces el producto cartesiano $G \times H$ es hamiltoniano

Teorema 3.16: Si $G$ es hamiltoniano y $S$ es el corte de vértices entonces

$$k(G-S) \leq |S|$$

Esto es lo que tengo hasta ahora

Supongamos que $G$ de orden $n$ y $H$ de orden $m$ son hamiltonianos . Sea $u \in V(G)$ y $v\in V(H)$ .

Sé que $G\times H$ tiene orden $nm$ y $deg(u,v)=deg(u) +deg(v) $

Pero quiero demostrar que $deg(u,v)=deg(u) +deg(v) \geq \frac{nm}{2}$ . ¿Cómo puedo hacerlo desde aquí? No creo que el teorema 3.16 ayude, porque no sé qué tipo de gráfico $G$ y $H$ son.

Answer 1

Muy revisado.

Su afirmación de que $\deg(\langle u,v\rangle)=\deg(u)+\deg(v)$ sugiere que el producto gráfico que tiene en mente es el Producto cartesiano que he visto denotado tanto por $\times$ y por $\square$ : $<\langle u_0,v_0\rangle$ y $\langle u_1,v_1\rangle$ son adyacentes en $G\times H$ si $u_0=u_1$ y $v_0$ y $v_1$ son adyacentes en $H$ o $v_0=v_1$ y $u_0$ y $u_1$ son adyacentes en $G$ . Si ese es el caso, no es difícil conseguir un ciclo de Hamilton en $G\times H$ de los ciclos de Hamilton en $G$ y $H$ .

Supongamos que $G$ tiene el ciclo $u_0,u_1,\ldots,u_m,u_0$ y $H$ tiene el ciclo $v_0,v_1,\ldots,v_n,v_0$ . Entonces podemos representar $G\times H$ por un $(m+1)\times(n+1)$ matriz rectangular de vértices, cada fila y columna de los cuales es un ciclo en $G\times H$ .

Si $n$ es impar, podemos conseguir un ciclo Hamilton como este:

$$\begin{array}{ccc} v_n&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\uparrow&&\downarrow\\ v_{n-2}&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ \vdots&\vdots&&\vdots&&\vdots&&\vdots&&&&\vdots&&\vdots&\\ v_1&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\color{blue}\uparrow&&&&&&&&&&&&\downarrow\\ v_0&\bullet&\color{red}\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &u_0&&u_1&&u_2&&u_3&&\ldots&&u_{m-1}&&u_m \end{array}$$

Si $n$ es uniforme, hacemos esto en su lugar:

$$\begin{array}{ccc} v_n&\bullet&\longrightarrow&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&\downarrow\\ v_{n-1}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\uparrow&&\downarrow\\ v_{n-2}&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet\\ &\uparrow&&&&&&&&&&\downarrow\\ v_{n-3}&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ \vdots&\vdots&&\vdots&&\vdots&&&&\vdots&&\vdots&\\ v_1&\bullet&&\bullet&\longleftarrow&\bullet&\longleftarrow&\ldots&\longleftarrow&\bullet&\longleftarrow&\bullet\\ &\color{blue}\uparrow&&\downarrow\\ v_0&\bullet&&\bullet&\longrightarrow&\bullet&\longrightarrow&\ldots&\longrightarrow&\bullet&\longrightarrow&\bullet&\color{red}\longrightarrow\\ &u_0&\color{red}\nwarrow&u_1&&u_2&&\ldots&&u_{m-1}&&u_m&&\color{red}\downarrow\\ &&&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow&\color{red}\longleftarrow \end{array}$$

En cada diagrama he comenzado en $\langle u_0,v_0\rangle$ y se dirigió a lo largo del borde azul, terminando a lo largo del borde rojo.