Que $G = (V,E)$ sea un árbol, entonces $G$ es que un caterpillar gráfico $\iff$ el gráfico de la línea de $G$ contiene un camino hamiltoniano.

Question

Aquí el gráfico de líneas $L(G)$ $G$ está definido por $L(G) := (E,\{ef : e,f \in E, e \bigcap f \neq \oslash\})$.

Creo que tengo un argumento para la dirección de avance. Si G es una oruga gráfico en $n$ vértices, entonces es un árbol donde todos los vértices están dentro de la distancia 1 de la ruta central. Así que si esta ruta tiene una longitud de $k$ construimos un nuevo camino de longitud $k-1$$L(G)$.

La etiqueta de los bordes en el camino simple $e_1, e_2, ..., e_k$ $G$ en el orden de la conectividad y la etiqueta de los vértices en el camino simple construido $v_1, v_2, ..., v_k$ respectivamente. A continuación, en cada par de vértices $(v_i,v_{i+1}), i = 1, 2, ..., k-1$, construir el grafo completo $K_{r}$ utilizando tanto $v_i$ $v_{i+1}$ $r-2$ nuevos vértices, donde $r$ es el número de aristas incidentes en el vértice en $G$ compartido por $e_i$$e_{i+1}$. Ya que cada grafo completo contiene un Hamiltoniano camino entre dos vértices, este gráfico de líneas se puede recorrer siguiendo un camino en el grafo completo de $v_i$ $v_{i+1}$cuando está disponible, y en caso contrario, ir directamente del $v_i$$v_{i+1}$. He olvidado algo?

Estoy luchando para llegar a las ideas para conversar.

Answer 1

DIBUJO: Si $G$ es un árbol w un camino Hamiltoniano, a continuación, $G$ es una oruga gráfico.

Deje $v$ ser un vértice de la distancia 1 de la máxima longitud de ruta de acceso de $P$$G$, y supongamos que $v$ $S$ conjunto de descendientes (todos los de $v$'s de los vecinos que no están en la ruta central). A continuación, vamos a $u$ $v$'s prójimo en el camino central. Entonces como $G$ es un árbol, no es exactamente un ejemplo $u$, y además en el gráfico de línea de $G$, el vértice $z_{uv}$ es un corte de vértice; de hecho, la eliminación de $z_{uv}$ recortes de los vértices $Z_S =\{z_{ab}; a,b \in S \cup \{v\}\}$ desde el resto de la gráfica. Por lo $\{z_{uv} \}+ Z_S$ deben ser contiguos vértices en uno de los extremos del camino Hamiltoniano.

Esto implica que (a) el gráfico de línea de $G'=G \setminus [S+\{v\}]$ tiene un camino Hamiltoniano $H'$ que termina en una arista incidente a $u$. Sin embargo, (b) cada arista $e$ incidente a $u$ $G'$ es un borde de corte con cada componente de $G \setminus \{e\}$ tiene al menos un borde. [De hecho, es suficiente para mostrar que $u$ no es un punto final de la ruta de $P$ ni es cualquier vecino de $u$$P$. Sin embargo, esto es así para que no $P$ no está de longitud máxima después de todo, de lo contrario deje $u'$ $u$'s prójimo en $P$ que es un extremo, entonces vamos a $P'= P -\{uu'\}+\{uv\}$ $+\{vv'\}$ donde $v'$ es un vecino de $v$ de la distancia de 2 de $P$.] Como (a) y (b) se contradicen entre sí, no hay ningún camino Hamiltoniano en $G$, después de todo.

---

Para la dirección de avance, básicamente se ve bien, pero es necesario que tenga en cuenta que $K_i$ $K_{i+1}$ intersectan exactamente un vértice, no sea que los caminos Hamiltonianos en $K_i$ $K_{i+1}$ se cruzan, además de en los extremos....es decir, las rutas de acceso en cada uno de los grupos tiene que cruzan precisamente en los extremos [y no más] y cubrir todos los vértices