¿Existe un gráfico general para cualquier secuencia de grado de hasta números naturales?

Question

Suponga que tiene un determinado grado de secuencia $(d_1,d_2,\dots,d_n)$ donde $d_i$ es incluso para cada $i$. ¿Existe un general gráfico con este grado de la secuencia?

Yo digo que sí, la forma más fácil es tomar ningún aislado gráfico de $n$ vértices, $\{v_1,\dots,v_n\}$, y, a continuación, en cada una de las $v_i$, pone en $d_i/2$ bucles, por lo $\deg(v_i)=d_i$ todos los $i$. Es esta la trampa? Parece muy fácil, y todo se basa en el hecho de que el gráfico se le permite tener múltiples aristas entre los vértices.

Como una pregunta, hay alguna manera, suficiente y/o condiciones necesarias para saber si una gráfica con un grado determinado de la secuencia existe, dado que la suma de los grados de la secuencia es aún? (No tiene que ser necesariamente el caso de que cada grado puede ser incluso a sí mismo.)

Answer 1

Lazos de uno hacer la pregunta algo sin interés. Si prohibirlos, la respuesta es dada por el Teorema de Erdős-Gallai.

Answer 2

Si usted está buscando un simple gráfico, la Erdos Gallai Teorema mencionado antes soluciona el problema. También hay otro teorema por Havel-Hakimi, que es más un algoritmo (y también construye una gráfica):

$d_1 \geq d_2 \geq d_3 ... \geq d_n$ es el grado de la secuencia de un gráfico si y sólo si

$d_2-1, d_3-1, ..., d_{d_1+1}-1, d_{d_1+2},..., d_n$ es un grado de la secuencia.

Debe estar bastante claro cómo construir la gráfica.

---

Para grafos:

Si usted permite que ambos bucles y varias aristas, cualquier secuencia de números, incluso con la suma de un cierto grado de secuencia. Para ver esto, dividir el impar de vértices en pares, añadir un borde para cada par y, a continuación, le quedan exactamente con el caso de cubiertos: todos los vértices tienen aún grado.

Creo que si no se permite que los bucles, pero que permiten múltiples aristas, se puede hacer si y sólo si la suma de los grados es aún más grande Y el grado es menor o igual a la suma de los remining vértice. La única que si debe quedar claro, mientras que el si puede ser probado de la siguiente manera: agregar un borde entre los dos grados más altos, muestran que el mayor grado aún es menor o igual a la suma de los remining vértices, y hacer de la inducción por la suma de los grados.

Answer 3

El teorema de Erdos-Gallai no solo prohíbe los bucles, sino también múltiples bordes. Uno puede ver los problemas de secuencia de grados en configuraciones donde uno quiere un gráfico conectado y se permiten múltiples bordes pero no bucles, etc. Aquí hay una referencia a un documento donde existen limitaciones en los bucles y bordes múltiples, pero se permiten "parcialmente": Una nota sobre la secuencia de Grado de Gráficos con Restricciones de FA Muntaner-Batle y M. Rius-Font (presentada para publicación).