Existencia de grafo k-regular

Question

En algunos ejemplos señaló que la existencia del gráfico de $k$-regular en números vértices es:

1. Es cierto por k o n incluso.
2. Falso, k y n impar. Pero podemos encontrar un gráfico y un vértice con grado de $n-1$ $k-1$ vértices con grado k. No existe un grafo k-regular de k y n impar porque $k=\deg(G) = 2|E(G)| / |V(G)|$ $|E(G)| = kn/2$ y $|E(G)|= m$ no son un número natural si $n$ $k$ es impar.

Alguna idea de prueba??

Answer 1

En el principio, usted debe asumir que $k < n$.

Si $n = 2m$ es, incluso, la construcción de un grafo con conjunto de vértices $$ \{ X_i : i \in \mathbb{Z}_m \} \cup \{ Y_i : i \in \mathbb{Z}_m \}, $$ where $\mathbb{Z}_m$ is the integers modulo $m$. Connect $X_i$ to $Y_j$ if $j-i \in \{1,\ldots,k\}$, where subtraction is done modulo $m$. Each $X_i$ is connected to $Y_{i+1},\ldots,Y_{i+k}$, and each $Y_j$ is connected to $Y_{j-1},\ldots,Y_{j-k}$.

Si $k = 2l$ es, incluso, la construcción de un grafo con conjunto de vértices $$\{X_i : i \in \mathbb{Z}_n\}.$$ Connect $X_i$ and $X_j$ if $i \neq j$ and $i-j \in \{-l,\ldots,l\}$. This relation is symmetric (since $j-i = -(i-j)$), and every $X_i$ is connected to $X_{i-l},\ldots,X_{i+l}$.

Como usted ha mencionado, cuando ambos $n,k$ son impares, tenemos $2e = nk$ donde $e$ es el número de aristas (esta fórmula se obtiene al contar todas las estaciones de todos los bordes), la cual es una contradicción.

Answer 2

Hay un teorema (Erdos-Gallai) sobre grado de secuencias:

$\displaystyle d_i$ es un grado de la secuencia de algunas gráfico si y sólo si

$\displaystyle \sum_{i=1}^{m} d_i \leq m(m-1) + \sum_{i=m+1}^{n} \min \{d_i, m\} \ \ \text{for} \ \ m \in \{1,2, \dots, n\}$

y

$\displaystyle \sum_{i=1}^{n} d_i$ es incluso.

Debe ser fácil de comprobar para el caso de al $\displaystyle d_i = k \ \ \forall i \in \{1,2, \dots, n\}$ (engorroso de verificación al final de la respuesta).

---

El caso de $\displaystyle k=n-1$, trivialmente conocer la existencia de un gráfico regular ($\displaystyle K_n$).

Supongamos $\displaystyle k \lt n-1$.

Ahora para $\displaystyle 1 \le m \le k$ tenemos que

$\displaystyle m(m-1) + (k-m)m + (n-k)k -mk = nk - k^2 - m \ge nk-k^2 - k = k(n-k-1) > 0$

Para $\displaystyle m \gt k$ hemos

$\displaystyle m(m-1) + (n-m)k - mk = m^2 - m(2k+1) + nk = (m-(2k+1)/2)^2 +nk - ((2k+1)/2)^2$

Para $k \lt n-1$ tenemos que $\displaystyle 4nk \gt 4k^2 + 4k$

es decir,$4nk \ge 4k^2 + 4k + 1 = (2k+1)^2$.

Por lo tanto $\displaystyle m(m-1) + (n-m)k - mk \ge 0$

Por lo tanto si $\displaystyle kn$ es incluso, existe una $k$-gráfico regular de n vértices.

La otra parte de ti.

Answer 3

Mucho más fácil: la suma de los grados es 2 | E |. Por lo tanto, la suma de los grados debe ser un número par. Como un tiempo impar un impar siempre es impar, y la suma de los grados de un gráfico k-regular es k * n, n y k no pueden ser ambos impares.