Construyendo una familia infinita de gráficos

Question

En un número de la teoría de grafos libros que estoy trabajando a través de venir a través de preguntas que pedir algo como $\textit{'Construct an infinite}$ $\textit{family of graphs with _________'}$ y el estado de alguna propiedad en el espacio en blanco que la familia de grafos han de satisfacer. Estas preguntas totalmente tocón de mí, así que mi pregunta es cuál, si alguna, es un buen método de ataque para estos tipos de preguntas? También lo que es una "solución" a estas preguntas pretende parece?

Como un ejemplo, actualmente estoy tratando de trabajar a través del siguiente problema de John Meier el libro de $\textit{Groups, Graphs and Trees; An Introduction to the Geometry of Infinite Groups}$ que le pregunta:

Construir una infinidad de distintos (2,3)-biregular gráficos

En este caso yo entiendo que lo que un biregular gráfico y puede construir un número de diferentes gráficos a mano, sin embargo, no entiendo cómo generalizar para obtener una infinidad de distintos gráficos de este tipo.

Answer 1

Si quieres construir una infinidad de gráficos, que se desea construir arbitrariamente grandes gráficos con la propiedad dada. Un enfoque sencillo a tratar sería la de tratar de encontrar una $n$-vértice de la gráfica para cualquier $n$.

Puede que esto no siempre funciona, porque no todos los valores de $n$ son válidos. Una familia infinita también le permite omitir los valores de $n$ que no funcionan, siempre y cuando usted todavía tiene $n$-vértice gráficos para infinidad de $n$. Por ejemplo:

• Si estás buscando ejemplos de $10$-regular gráficos, usted no sería capaz de encontrar ninguna por menos de $11$ vértices. Está bien para saltar $n=1, 2,\dots, 10$.
• Si estás buscando ejemplos de $3$-regular gráficos, usted no sería capaz de encontrar ninguna para un número impar de vértices. Está bien tomar sólo $n=2, 4, 6, 8, \dots$.
• Incluso la búsqueda de un gráfico de algún tipo, por ejemplo, $2^{2^k}$ vértices para cada una de las $k$ es todavía una familia infinita, mientras lo suficientemente grande $k$ obras.

En su caso, hay una restricción: $(2,3)$-biregular gráfico ha $3k$ vértices de un lado, y $2k$ vértices en el otro, para algunas de las $k$. Así que usted puede tratar de encontrar un ejemplo de una $5k$-vértice $(2,3)$-biregular gráfico para cada $k$, y que le daría una familia infinita.

(O usted podría descubrir otra restricción, especificar que los valores de $n$ trabajar de forma más precisa, e inténtelo de nuevo.)

En algunos casos, parte del desafío podría estar describiendo cómo se puede lograr el ejemplo. Este sería el aspecto de un algoritmo: dado $k$, aquí es cómo se construye una $5k$-vértice de la gráfica con la propiedad que desea.

Answer 2

La respuesta a tu problema es bastante fácil. Observar que si $K_{2,3}$ es el $(2,3)$-biregular gráfico con $5$ vértices, a continuación, las distintas unión de $n$ $K_{2,3}$ es $(2,3)$-biregular gráfico con $5n$ vértices.

Una forma más general para atacar el problema, donde se puede ver la heurística es la siguiente:

Deje $G=(V,E)$ ser $(2,3)$-biregular gráfico con piezas de $B$ e $C$, donde $\forall b\in B \ \deg_G b=2$ e $\forall c\in C \ \deg_G c=2$. Es fácil ver que $2|B|=3|C|$. De hecho, podemos contar el número de aristas de $G$ en dos formas diferentes de la siguiente manera: el número de aristas de $G$ que es el incidente a algún vértice en $B$ es igual a $2|B|$, mientras que el número de bordes de $G$ que es el incidente a algún vértice en $C$ es igual a $3|C|$. Por lo tanto, desde cada borde de $G$ es entre un vértice en $B$ y un vértice en $C$ tenemos la igualdad, es decir, $2|B|=|E|=3|C|$. Es fácil resolver esta ecuación Diophantine. Tenemos que $|B|=3n$ e $|C|=2n$ para algún entero positivo $n$.

Por lo tanto, usted ha restringido considerablemente el problema de encontrar $(2,3)$-biregular grafos bipartitos gráficos de las piezas de tamaños de $3n$ e $2n$ respectivamente.

Este ejemplo no es tan interesante, ya que tiene una fácil solución, pero en general, la estrategia para enfrentar este tipo de problemas es poco a poco restringir la estructura de la gráfica de ser considerada. En muchos de estos problemas de una manera agradable para la construcción de la familia de grafos es por inducción. En este ejemplo se esconde una inducción en la construcción de los gráficos, pero es trivial!

Answer 3

La pregunta en su primer párrafo es demasiado amplio; es casi como preguntar "¿Cómo puedo encontrar un gráfico que satisface ciertas condiciones?" La diferencia es, que estás preguntando "¿Cómo puedo encontrar un gráfico que satisface ciertas condiciones, donde una de las condiciones es mas de $n$ vértices'?" La pregunta es incontestable porque lo que da el problema, su sabor no es la parte acerca de tener más de $n$ vértices, de las demás condiciones. Si usted solicite una pregunta general, la mejor que puede esperar es una respuesta muy general, como "Pensar en ello."

Su pregunta acerca de la $(2,3)$-biregular gráficos es el tipo que podemos tratar aquí. Como se ha dicho, es muy fácil: basta con pensar en la gráfica de $nK_{3,2}$, la unión de $n$ vértice disjuntos copias completas de las bipartito gráfico de $K_{3,2}$. Para hacerlo un poco más interesante, permite pedir grande conectada $(2,3)$-biregular gráficos. Todavía hay un montón de soluciones. He aquí uno:

Dibujar un $n\times n$ tablero de ajedrez, $n\ge3$. Dividir cada pequeño cuadrado en dos triángulos trazando una diagonal. Hacer el tablero de ajedrez en un toro por la identificación de la izquierda con la derecha y la parte superior con la parte inferior. Ahora cada una de las $2n^2$ triángulos ha $3$ lados, y cada una de las $3n^2$ bordes es un lado de la $2$ triángulos, por lo que el triángulo de borde de incidencia gráfica es una $(3,2)$-biregular gráfico de la orden de $5n^2$.