¿Se puede proyectar la gráfica $X$ al camino $P_{d(X)}$?

Question

Sea $X$ una gráfica con diámetro $d$. Sea $P_d$ la gráfica "camino de longitud $d$", es decir, la gráfica con vértices $\{0,1,\ldots,d\}$ y aristas de la forma $\{i,i+1\}$ con $i=0,1,\ldots,d-1$.

¿Existe un morfismo de gráficas sobreyectivo $f:X\to P_d$?

Estoy pensando en gráficas simples y los morfismos son aquellas funciones que mandan vértices adyacentes en vértices adyacentes o en el mismo vértice (si exijo que sea a vértices adyacentes $K_3$ es contraejemplo).

Comments

Es "$d$" en lugar de "$n$", ¿no?

---

Ya está corregido. Gracias.

Answer 1

Sí. Toma dos vértices que sean testigos de que el diámetro es $d$ y ua trayectoria de longitud $d$ entre ellos. Abusivamente llama $0,1,2,\dots,d$ a los vértices de esta trayectoria. El morfismo que manda al vértice $x$ en el vértice $d(0,x)$ funciona.

Comments

Y qué haces con los demás vértices que no están en la trayectoria?

---

A lo mejor no quedó claro de mi respuesta, explico más: a cualquier vértice $x$, en la trayectoria o no, le calculas su distancia $d(x,0)$ al vértice que llamaste $0$ y proyectas $x$ en el vértice etiquetado con el número $d(x,0)$.

---

En mi cabeza, lo que haces es "colgar" la gráfica desde el vértice 0 y cada vértice se proyecta en la trayectoria según que "tan abajo" quedó cuando colgaste la gráfica.

---

Ya: pensando al vértice 0 como el "origen" estás mandando cada vértice a su norma. Entonces la desigualdad del triángulo te dice que si $ab $ es una artista $||a|-|b||\leq 1$, lo que en $P_d$ quiere decir que $|a|$ y $|b|$ son adyacentes o iguales.