Especial Vértice De Partición

Question

Cuando podemos partición de los vértices de un grafo $G$ a $n$ subconjuntos tales que cada vértice es adyacente al vértice de cada subconjunto? Por ejemplo, en el siguiente gráfico, se ha dividido los vértices en $2$ subconjuntos.

Se sabe algo de este tipo de partición? Una motivación para el estudio de estos partitionings es que podemos representar los vértices como sea posible, los estados y los vértices adyacentes de los estados accesible a través de un movimiento. A continuación, esta división nos permite transmitir ciertos mensajes no importa lo que el estado.

Answer 1

Denotamos como $N(G)$ máximo $n$, ya que tal partición existe. Entonces es claro que una partición existe también para todos los $n\le N(G)$. Disponemos de los siguientes límites simple para $N(G)$.

$\chi(G)\le N(G)\le V(G)$ donde $V(G)$ es el número de vértices del grafo $G$ $\chi(G)$ es un cromática número de la gráfica de $G$, que es el mínimo número de colores necesarios para colorear todos los vértices del grafo $G$ tal de que no hay ningún adyacentes monocromática vértices.

$m(G)\le N(G)(N(G)-1)/2\le E(G)$ donde $E(G)$ es el número de aristas del grafo $G$ $m(G)$ es un número de aristas de un máximo de coincidencia de la gráfica de $G$, que es el número máximo de mutuo no adyacentes a los bordes de la gráfica de $G$.

El límite superior $N(G)\le V(G)$ parece ser un corolario de la envolvente $N(G)(N(G)-1)/2\le E(G)$, debido a $E(G)\le V(G)(V(G)-1)/2$ (supuse que el gráfico de $G$ no tiene doble los bordes).

Los límites superiores están lejos de ser óptimo, ya que un gráfico de $G$ con grandes tanto en $V(G)$ $V(G)$ puede tener pequeñas $N(G)$. Por ejemplo, si $S_n$ es la estrella con $n$ vértices (el árbol con una raíz y $n-1$ hojas), a continuación,$V(S_n)=n$, $E(S_n)=n-1$, mientras que $N(S_n)=2$.