Incluso bicolor de gráficos regulares.

Question

Estoy interesado en exhaustivamente de representación en el cuarto grado (4-regular) gráficas simples de orden creciente y bi-color negro y blanco, que el barrio cerrado de cada vértice contiene un número par de negro vértices. Aquí, el barrio cerrado de un vértice se define como el vértice, además de sus vértices adyacentes.

No trivial (no 'blanco') ejemplo de ello es la cuártica gráfico de la orden de los cinco ($K_5$, el grafo completo con 5 vértices) con dos o cuatro vértices de color negro y el resto de color blanco.

Cómo generar no trivial gráficos de orden superior? Se puede hacer esto de forma exhaustiva?

Answer 1

Puedes usar el siguiente programa Sage para obtener cierta intuición en tu problema. La función checkGraphs (n) itera sobre todos los 4 gráficos regulares del pedido$n$ y escribe los gráficos respectivos y el primer colorante legal que encuentra.

 def hasProperty(G,c):
    for v in G:
        if (c[v]+sum(c[u] for u in G[v])) % 2 == 1:
            return false
    return True

def isGood(G):
   for s in subsets(G):
        c = {v:0 if v in s else 1 for v in G}
        if hasProperty(G, c): 
            return c 
    return false
def checkGraphs(n):
    for G in graphs.nauty_geng("-d4 -D4 " + str(n)):
        print isGood(G), G.edges(labels=false)
 

Por ejemplo

 sage: checkGraphs(7)
{0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1} [(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 5), (4, 6)]
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} [(0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 6)]
 

** Editar Aquí hay una gráfica de todos estos gráficos y los colorantes respectivos.

Answer 2

He venido para arriba con algunas construcciones para la generación de gráficos con más vértices;

1) Si hay un conjunto de 2 negro vértices que se ajusta a la propiedad en un gráfico, a continuación, es sencillo probar que deben provenir de un subgrafo isomorfo a $K_2 + 3K_1$ (conocido anteriormente como una $K_5 - K_3$). Mediante esto podemos añadir 3 vértices a cualquier gráfico de $G$ y tienen la propiedad de la siguiente manera:

Tomar cualquier ruta en 4 blanco vértices $v_1$, $v_2$, $v_3$ y $v_4$$G$, eliminar los bordes de la ruta de acceso y agregar nuevos vértices y aristas como muestra la figura. Todos los nuevos vértices tendrá dos negros (verde) vértices en sus barrios como le $v_2$$v_3$, todos los demás tendrán sus números originales.

Para $K_5$, elijamos a toda su coloración blanca y el camino 5-2-3-6 con el 5º vértice 4. Podemos quitar los bordes de 5-2, 2 y 3 de 3-6 y agregar vértices 1, 7 y 8. Añadimos los bordes de 1, 2 y 3 a la 7 y 8, y también una ventaja de 7 a 8 y los bordes del 1 al inicio y al final de la ruta original, 5 y 6. Esto le da a la única gráfico con 8 vértices con su propiedad.

El mismo razonamiento también funciona si empezamos con un triángulo blanco vértices y agregar dos vértices; por ejemplo, con $K_6 - 3K_2$ elegimos triángulo 1, 2 y 3, quite los tres bordes de la misma y añadir en dos vértices (7 y 8) uno al lado del otro y 1, 2 y 3.

2) Tomar cualquier 3-regular el gráfico de $2n$ vértices y el color de cada vértice negro; necesariamente satisfacen la propiedad de tener un número par de negro vértices en el barrio cerrado de cada uno de sus vértices. Ahora tome ninguna 4-gráfico regular para ser el blanco de los vértices y subdividir $n$ bordes y añadir nuevas aristas a partir de este nuevo valencia de 2 vértices a algunos negros vértices.

Considerando el caso general:

Teorema: El subgrafo $B$ inducida por el negro vértices debe contener sólo los vértices de valencia impar.

Prueba: Considere la posibilidad de cualquier vértice $v$$B$; necesitamos $|N[v]|$, incluso para satisfacer la propiedad, por lo $|N(v)|$ debe ser impar, pero que es la valencia de $v$.

Corolario: siempre debe haber un número par de vértices en $B$.

Para el caso general de generar todos los gráficos con la propiedad con $n$ vértices podemos hacer uno de los siguientes basado en las ideas anteriores:

a) Construir todos los 3-regular los gráficos de la orden de $b \leq \lfloor \frac{4n}{5} \rfloor$, y luego considerar maneras de agregar $b$ bordes para el resto de $n-b$ vértices para preservar 4-regularidad y asegúrese de que cada blanco de vértices está unido a 0, 2 o 4 negro vértices. Ahora la construcción de todos los gráficos con todos los vértices de valencia 3, aparte de uno de valencia 1 add blanco vértices de nuevo. Sigue repitiendo este proceso hasta que llegamos al caso de la negra vértices formando un 1-gráfico regular en cuyo caso sabemos que los barrios de cada uno de estos bordes es una $K_2 + 3K_1$.

Sin embargo, esto necesariamente va a traer un montón de duplicación de esfuerzo, ya que la mayoría de los gráficos de color negro subdiagramas de diversos órdenes, y también hay muchas maneras diferentes para unirse a la de blanco y negro vértices juntos y algunos de estos se llevan a isomorfo gráficos también.

b) Alternativamente, se puede utilizar un proceso recursivo para generar 4-regular los gráficos de la orden de $n$ de los de ligeramente más pequeñas órdenes (en su mayoría de $n-1$):

En la literatura existen algunos resultados publicados como "la Construcción de la cuártica gráficos", S Toida (Revista de Teoría Combinatoria, de la Serie B, Volumen 16, número 2, abril de 1974, Páginas 124-133) y, más en general (con referencias útiles para las pequeñas valencia) "La generación de r-regular gráficos"; Guoli Ding, Peter Chen (Discreta Matemática Aplicada Volumen 129, Problemas De 2-3, 1 De Agosto De 2003, Páginas 329-343).

Mi preferencia sería el uso de la operación, la cual, dado un 4-gráfico regular $G$, elige dos bordes sin ningún vértice en común en $G$, elimina los dos bordes y añade un nuevo vértice $u$ adyacente a los cuatro vértices de la eliminan los bordes. Tenga en cuenta que si todos los 4 vértices son de color blanco en la coloración $G$ a continuación, el nuevo gráfico también tiene su propiedad con $u$ también de color blanco.

Las únicas circunstancias en las que un gráfico no se puede formar por medio de esta operación es aquel en el que todos los vértices tienen muchas aristas en el subgrafo inducido por la vecindad de cada vértice. Esto significa que vamos a tener $K_2 + 3K_1$ subdiagramas (que garantiza la propiedad) o $K_4$s. Con un $K_4$ normalmente, es posible reducir a un solo vértice $v$ y luego, si el gráfico resultante tiene la propiedad y $v$ es blanco, podemos garantizar que el gráfico original tiene la propiedad también.

Todavía hay algunos pequeños problemas para trabajar a través de para obtener una clasificación completa, pero espero que esto te da nuevas formas de generar estos gráficos.

Answer 3

No es realmente una solución, pero creo que una idea importante.

Si vemos la 2-colorantes, como los mapas desde el vértice conjunto de a $\mathbb{Z}/2\mathbb{Z}$ envío de negro vértices 1 y blanca vértices a 0, entonces el espacio de todos 2 los colorantes fijos en un gráfico de forma un espacio vectorial por pointwise adición. La condición de que el barrio tiene un número par de negro vértices se traduce en una ecuación lineal homogénea, por lo que, en particular, el espacio de la buena colorantes es un subespacio vectorial. Por lo tanto, no siempre va a ser una potencia de 2 número de dichos colorantes.

Deje $A$ ser la matriz de adyacencia del grafo, entonces estas ecuaciones lineales son sólo de la forma $(A+I)x=0$ donde I es la matriz identidad y $x$ es un vector que indica que los vértices damos color. De manera que la gráfica tiene un trivial buena coloración iff la matriz $A + I$ no tiene rango completo de más de $\mathbb{Z}/2\mathbb{Z}$ lo que significa que $A+I$ tiene incluso determinante. Como lejos al describir los gráficos de este tipo se va, yo estoy en una pérdida.