Diseñar un gráfico conectado con diámetro más pequeño

Question

Deje $G_k$ ser cualquier gráfica conectada con $2^k$ vértices y el grado de cada vértice se $k$. Cómo diseñar un $G_k$ con menor diámetro?

El límite inferior del diámetro más pequeño puede ser estimada (inspirado por Sfarla): \begin{align*} 2^k &\leq 1+k+k(k-1)+\ldots+k(k-1)^{d-1}\\ &= 1+k\frac{(k-1)^d-1}{k-2}\\ \end{align*}por Lo tanto, \begin{align*}d &\geq \log_{k-1}\left\lceil \frac{(2^k-1)(k-2)}{k}+1 \right\rceil\\ &= O\left(\frac{k}{\log_2k}\right) \end{align*}

Los tres primeros gráficos son:

Answer 1

Observe que para $k>1$ el diámetro de la $d$ de un grafo no dirigido con $2^k$ vértices y $k2^{k-1}$ bordes siempre es mayor que $1$. Esto es debido a que no puede ser completo.

Por otra parte, vamos a $n$ $e$ ser enteros positivos, siempre que $e \geq n-1$, siempre se puede diseñar un grafo no dirigido con $n$ vértices y $e$ bordes cuyo diámetro es en la mayoría de las $2$. Por ejemplo, supongamos $G=(V,E)$, con

$$V=\left\{x_1, \ldots, x_n \right\},$$

e imponer que el conjunto

$$ \left\{(x_1,x_i)\,|\, i=2,\ldots, n\right\} \subseteq E.$$

A continuación, la distancia entre cada par de vértices está en la mayoría de los $2$.

Esto debe responder a su pregunta, ya que el diámetro más pequeño es$2$$k>1$.