El vértice de menor excentricidad no puede tener la mayor distancia promedio

Question

La excentricidad de un vértice $\epsilon (v) $ es la máxima de las distancias $d(v, u) $ sobre todos los demás vértices $u$. La distancia promedio de un vértice avgd$(v) $ es el promedio de todos los $d(v, u)$, más precisamente $avgd(v) =\frac{\sum_{u\neq v} d(v, u)} {|V|-1}$

Ahora, si el centro de un grafo es un solo vértice $v$, es decir, hay un vértice de menor excentricidad $v$, entonces $\epsilon (v) <\epsilon (u), u \neq v$, entonces avgd$(v) < \max(avgd(u)_{u \in V}) $ porque este vértice $v$ no puede tener al mismo tiempo la mayor distancia promedio.

Por lo menos, eso es lo que asumo. Mi intuición proviene de un grafo donde una pequeña clique y una gran clique están conectadas con un vértice separado. Ese vértice es entonces el de menor excentricidad, pero los vértices de la pequeña clique siempre tienen una distancia promedio mayor. ¿Alguien tiene una demostración o un contraejemplo?

Algunos de mis pensamientos sobre esta conjetura:

Me doy cuenta ahora de que un grafo compuesto por un solo vértice sería un contraejemplo trivial, por lo tanto consideremos solo grafos conectados simples con más de un vértice.

Generé muchos grafos con un solo vértice como centro y efectivamente siempre pude encontrar un $u$ con distancia promedio estrictamente mayor que el centro. Me pregunté si también podemos encontrar un $u$ que sea adyacente al centro, pero no siempre es el caso.

Aunque pueda sonar intuitivo o trivial que el punto más central no sea el punto con la mayor distancia promedio, no es generalmente el caso para cualquier métrica. No es generalmente cierto para la distancia euclidiana, por ejemplo.

Pensé que podría ser cierto porque si hay un centro singular $ v$, entonces algún $v*$ tiene un camino más corto a través del centro para más de la mitad de los otros vértices. Pero resultó ser falso, encontré grafos con un centro singular pero sin tal $v*$

Answer 1

Contraejemplo. Tomemos $6$ conjuntos de vértices disjuntos de $2$ elementos $V_i=\{x_i,y_i\}$ ($0\le i\le5$); dibujamos $30$ aristas haciendo que $V_i\cup V_j$ sea una clique para $i-j\equiv1\pmod6$; se añade un $13^\text{er}$ vértice $z$ y las aristas $y_0z$ y $y_3z$. Se puede verificar fácilmente que en este grafo $$\epsilon(z)=2;$$ $$\epsilon(x_i)=\epsilon(y_i)=3;$$ $$\operatorname{avgd}(z)=\frac{22}{12};$$ $$\operatorname{avgd}(y_0)=\operatorname{avgd}(y_3)=\frac{19}{12};$$ y para vértices $v\notin\{z,y_0,y_3\}$, $$\operatorname{avgd}(v)=\frac{21}{12}.$$ Generalizando esta construcción, para enteros $k\ge1$ y $n\ge2$ hay un grafo de orden $(4k+2)n+1$, radio $2$ y diámetro $3$, con un vértice único $z$ de excentricidad $2$ que tiene distancia promedio $$\operatorname{avgd}(z)=\frac{2(4k+2)n-2}{(4k+2)n}=2-\frac1{(2k+1)n}$$ mientras que $$\max_{v\ne z}\operatorname{avgd}(v)=\frac{(6k+4)n+1}{(4k+2)n}=\frac32+\frac{1+\frac1n}{4k+2}.$$ Para esto tomamos $(4k+2)n$ vértices, divididos en $4k+2$ "blobs" de $n$ vértices cada uno; se colocan los bloques en un círculo; se une cada vértice con todos los demás vértices en su propio bloque y los $k$ bloques más cercanos a cada lado; finalmente se añade un vértice central $z$ y se une con dos vértices que están en bloques diametralmente opuestos.