Una pregunta sobre la construcción de un gráfico.

Question

Estaba haciendo el seguimiento de la construcción. Sabemos $C_4$ y $C_5$ son $2$ -Gráficos autocentrados. Cuando añadimos un nuevo vértice $x$ y $y$ a $C_4$ y $C_5$ resp, (mostrado en la fig) el nuevo gráfico contiene exactamente dos vértices con excentricidad tres y el resto con excentricidad dos. Tenía curiosidad por saber si proponemos una construcción similar en la que la excentricidad de cada vértice sea tres y sólo un vértice con excentricidad dos, utilizando los mismos grafos $C_4$ y $C_5$ . Añadiendo uno o dos vértices de manera que los gráficos resultantes contengan $C_4$ y $C_5$ y como subgrafos inducidos. Cualquier sugerencia será apreciada. Muchas gracias.

Nota : A gráfico egocéntrico es un gráfico donde la excentricidad de cada vértice es la misma.

Answer 1

Buscamos un gráfico $G$ con las excentricidades deseadas y que contienen $C_5$ como un subgrafo inducido. Empezaremos con el subgrafo inducido $C_5$ subgrafo y añadir un vértice. Claramente, $G$ debe estar conectado, y sólo hay una forma de añadir una arista para conectar el nuevo vértice, hasta el isomorfismo.

Los vértices de excentricidad $2$ están rodeados por un círculo. Como las aristas adicionales no pueden disminuir la excentricidad y el gráfico tiene demasiados vértices de excentricidad $2$ El único vértice extra es insuficiente. Añadimos un segundo vértice. Volvemos a añadir una arista para la conectividad, y hay cuatro formas no isomórficas de hacerlo.

Con un razonamiento similar al anterior, los dos gráficos superiores no serán suficientes. Los dos gráficos inferiores tienen vértices con excentricidad $4$ por lo que son necesarias aristas adicionales, pero se puede comprobar que no se puede añadir ninguna arista (manteniendo el $C_5$ inducido) sin crear un vértice adicional con excentricidad $2$ por lo que ninguna de las dos gráficas es suficiente. Por lo tanto, al menos $3$ son necesarios vértices adicionales.

Abajo a la izquierda hay un gráfico con $C_5$ como un subgrafo inducido y $3$ vértices añadidos de forma que el vértice rodeado tenga excentricidad $2$ y todos los demás vértices tienen excentricidad $3$ que satisface las propiedades deseadas. De forma similar, se puede demostrar que $3$ los vértices deben añadirse a $C_4$ para satisfacer las propiedades deseadas, y el gráfico de abajo a la derecha muestra que $3$ es suficiente.