Dado el gráfico grado secuencia . Cuál es la condición que puede ser grado secuencia de gráfico conectado. ¿Alguien puede por favor compartir link de Teorema?
Respuesta
¿Demasiados anuncios?
Tenga en cuenta que hay dos nociones de aquí que se debe distinguir: potencialmente y por la fuerza de realización de las secuencias.
Deje $d=(d_1,\ d_2,\ \cdots,\ d_n)$ ser un grado de secuencia, cada vez más ordenados $$d_1 \le d_2 \le \cdots \le d_n$$
Decimos que $G$ es una realización de $d$ si el grado de la secuencia de $G$ es igual a $d$.
Decimos que $d$ está conectado a la fuerza si cada realización de $d$ está conectado.
Decimos que $d$ es potencialmente conectado si existe una realización de $d$ que está conectado.
De forma análoga definiciones se mantienen para cualquier propiedad $P$ de los gráficos, en el que se dice que una secuencia $d$ es potencialmente/forzosamente $P$-realizable si algunas/todas realización de $d$ satisface $P$. Hay algunos hermosos resultados relacionados con dichas secuencias. En relación a la conectividad, aquí están algunos de los resultados básicos.
Teorema 1 (Bondy y Boesch): Vamos a $d=(d_1,\ \cdots,\ d_n)$ ser un grado de secuencia. Deje $k$ ser un entero tal que $1\le k \le n-1$. Si $$d_i \le i + k - 2 \implies d_{n-k+1} \ge n-i$$ para$1 \le i \le \left\lfloor \frac{n-k+1}{2}\right\rfloor$, $d$ es forzosamente $k$-conectado.
Teorema 2 (Bauer, Hakimi, Kahl, Schmeichel): Vamos a $d=(d_1,\ \cdots,\ d_n)$ ser un grado de secuencia. Deje $\lambda \ge 1$ ser un número entero. Si $d_1 \ge \lambda$ y $$d_{i-\lambda+1} \le i - 1 \land d_i \le i +\lambda -2 \implies d_n \ge n-i+\lambda-1$$ para$\lambda+1 \le i \le \left\lfloor\frac{n}{2}\right\rfloor$, $d$ es forzosamente $\lambda$-edge-conectado.
Teorema 3: Deje $d = (d_1,\ \cdots,\ d_n)$ ser un grado de secuencia. A continuación, $d$ es potencialmente conectado si y sólo si $d_1 \ge 1$ y $$\sum_{i=1}^nd_i \ge 2(n-1)$$
Teorema 4 (Edmonds): Vamos a $d = (d_1,\ \cdots,\ d_n)$ ser un grado de secuencia. A continuación, $d$ es potencialmente $\lambda$-edge-conectado ($\lambda \ge 2$) si y sólo si $d_1 \ge \lambda$.
Teorema 5 (Wang Y Kleitman): Vamos a $d = (d_1,\ \cdots,\ d_n)$ ser un grado de secuencia. A continuación, $d$ es potencialmente $k$-conectado ($k\ge 2$) si y sólo si $d_1 \ge k$ y $$\frac{1}{2}\sum_{i=1}^n d_i - \sum_{i=n-k}^n d_i + \frac{(k-1)(k-2)}{2} \ge n-k$$
También es interesante el resultado con respecto a grado de conjuntos, es decir, las multiplicidades de los términos no están especificados.
Teorema 6 (Kapoor, Polimeni Y de la Pared): Vamos a $S=\{s_1,\ \cdots,\ s_k\}$ ser un conjunto de enteros positivos. A continuación, $S$ es realizable como el grado de un grafo conexo. Por otra parte, podemos tomar la orden de la gráfica se $M+1$ donde $M$ es el miembro más grande de $S$.
Referencias (por el teorema de número):
1 y 2: Bauer, Hakimi, Kahl, Schmeichel. Grado suficiente las Condiciones para $k$-Arista-Conectividad de un Grafo.
3: Berge, Gráficos y Hypergraphs. El resultado no es demasiado difícil demostrar el uso de la inducción. Hay bastantes otros resultados interesantes dado en Berge del libro. Especialmente relevantes son las secciones de los capítulos 6 y 9.
4: Edmonds, la Existencia de $k$-edge-conectado ordinario gráficos con lo prescrito grados.
5: Wang, Kleitman. Sobre la existencia de la N-conectado gráficos con lo prescrito grados ($n \ge 2$).
6: Kapoor, Polimeni, De La Pared. Grado de conjuntos de gráficos, Fondo. De matemáticas. 95 (1977) 189-194.
