Una pregunta en gráficos con todos los vértices es central o periférico

Question

Si sólo hay dos vértices y el resto de periféricos. Podemos deducir que el centro de los vértices son siempre adyacentes? Tengo ejemplos siguientes (excentricidad mencionado), desde donde he propuesto esto. Es allí cualquier contra-ejemplo para esto? Cualquier sugerencia o sugerencia es cordial bienvenida. Gracias por la ayuda.

Un ejemplo más :

Answer 1

Si no me equivoco, este es un ejemplo contrario:

Los vértices negros son centrales y no adyacentes. Todos los demás vértices son periféricos. Los colores coincidentes muestran que los vértices correspondientes son de distancia 3. El diámetro de los gráficos también es 3.

Answer 2

He encontrado otra solución, que podría ser mucho más satisfactorio que un contraejemplo, como en mi otra respuesta. Así que me decidí a escribir una nueva respuesta.

He encontrado una manera de construir una gráfica de diamater $n\geq 4$ y radio de $n-1$ con exactamente dos vértices. Este es un contraejemplo a su pregunta, así como a su conjetura en el comentario de abajo de mi otra respuesta, ya que esto significa que podemos hacer que la distancia entre la central de vértices tan grande como queramos. La idea principal es comenzar con un gráfico de diámetro $n$ y, a continuación, quitar algunos vértices para reducir la excentricidad de dos vértices.

Comience con el borde de la gráfica de la hipercubo $Q_n$ (el gráfico que consta de los nodos que representan las secuencias binarias de longitud $n$, dos nodos que se están adyacentes si y sólo si sus secuencias difieren en un solo dígito). $Q_n$ $2^n$ vértices y es de diámetro y el radio de $n$. Ahora, elige dos no antipodal vértices $v,w\in V(Q_n)$, es decir,$d(v,w)<n$. Podemos optar $d(v,w)=n-1$. Estos vértices será nuestra central de los vértices en la gráfica final. Tenga en cuenta que a $Q_n$ cualquier vértice $u$ tiene un único antipodal vértice $u'$, es decir, un vértice de distancia $n$. Construimos nuestra gráfico final, $G$ mediante la eliminación de $v'$$w'$$Q_n$. Ahora, $G$ es de diámetro $n$, radio $n-1$ con exactamente dos vértices $v,w$ de pie $n-1$ a cada uno de los otros.

Esto es lo que este se ve como en el caso de la 4-dimensional hipercubo, es decir,$n=4$:

El gráfico es de diámetro de 4 y de radio 3. El negro vértices son centrales y de la distancia de 3 de cada uno de los otros. Juego con los colores indican que los vértices correspondientes son antipodal, por tanto, definir el diámetro del grafo.

La restricción $n\ge 4$ es necesario, porque de lo contrario podría ocurrir que dos anteriormente antipodal vértices no están unidos por un camino de longitud $n$. Tenga en cuenta que este enfoque también podría ser generalizado a $r$ central de los vértices, pero entonces no tiene que ser de las investigaciones sobre el límite inferior de $n$ depende de $r$.