Contar el número de gráficos no-isomorfo de la secuencia de determinado grado

Question

¿Hay simples gráficos G y H ambos con grados de vértice 2,2,2,2,3,3 tal que G y H no son isomorfos? Si es así, dibujarlos, de lo contrario, explicar por qué no existen.

Tengo problemas para responder a esta pregunta. Sé que esta secuencia es gráfica, pero cómo puedo saber sean cuántos hay que no son isomorfos y cómo dibujarlos. ¿Alguien puede por favor ayudar?

¡Gracias!

Answer 1

Sí, hay. Voy a describir dos de tales gráficos.

En primer lugar, organizar los seis vértices en un 2 por 3 cuadrícula. A continuación, conecte los vértices para formar el número de $8$ como se ve en los deportes de marcadores o algunos de los relojes digitales. Esto es lo que un comentarista se refiere a como un theta grafo.

Para el segundo ejemplo, llamar a los vértices de grado $3$ $A$ y $B$ y los otros cuatro $x,y,z,w$. Set $A$ adyacente a $x,y,z$, $B$ adyacente a $x,y,w$, e $z$ adyacente a $w$.

En el primer ejemplo, el grado $3$ vértices son adyacentes, pero en la segunda no lo son, así que los dos grafos no son isomorfos.

Answer 2

Vértices de grado 2 son bastante interesantes como pueden ser removidos de un gráfico mediante la combinación de sus dos bordes en uno.

Supongamos que hicieron que a su gráfico(s), entonces usted podría quedar con un gráfico con dos vértices de grado 3. Solo hay un gráfico simple, ya que cada borde tiene que conectar los dos vértices.

Ahora inserte los cuatro vértices de grado 2 de la espalda de nuevo. Usted puede distribuir de ellos a lo largo de las tres aristas en varias formas distintas. Como las tres aristas del grafo reducido son equivalentes, todo lo que importa es cómo dividir los cuatro vértices añadidos en tres grupos (algunos de los cuales pueden tener cero vértices). Hay cuatro maneras de hacer esto: 0+0+4, 0+1+3, 0+2+2, o 1+1+2. Esto le da cuatro no isomorfos gráficos.

Answer 3

Dibuja dos hexágonos. En uno, dibuja un acorde que lo divide en dos y en otro, dibujar un acorde que no. Entonces obtendrá dos gráficos nonisomorphic porque uno tiene un circuito simple de longitud $4$ y el otro no.

Answer 4

Sí, es posible ver la imagen de abajo y no son isomorfos entre sí debido a la segunda grafo contiene un ciclo de longitud 3 (4-5-6-4), donde como primer gráfico no tiene un ciclo de longitud 3.

Número de no isomorfos gráficos = número Total de gráficos con el grado determinado de la secuencia número total de grafos isomorfos $(4! \times 2!)$.