Así que estoy buscando en un papel por Rosenfeld, "En un problema de C. E. Shannon, en la teoría de grafos", donde se da condiciones necesarias y suficientes para un gráfico de $H$ a satisfacer $$\alpha(G \boxtimes H) = \alpha(G) \alpha(H) \qquad (1)$$ para todos los gráficos de $G$. Aquí, $\alpha$ representa el número de independencia, y $\boxtimes$ representa el producto fuerte. Pero, lo hace en términos de programación lineal que no soy bueno. Así que, me pregunto si lo que él hizo corresponde a algún conocido gráfico de parámetro. A continuación transcribo la parte pertinente del documento para su finalización.
Deje $G$ ser finito gráfico. $V(G) = \{g_1, \ldots, g_n\}$. Deje $\{C_1, \cdots, C_s\}$ ser un orden fijo de todas las diferentes camarillas de $G$. Definir $y_i^{(j)}$ 1 exactamente al $g_i \in C_j$, y 0 en caso contrario. También, vamos a $$ P_G = \left\{(x_1, \ldots, x_n) \quad \left| \quad\sum_{i = 1}^n y_i^{(j)} x_i \leq 1, \quad x_i \geq 0, \quad 1 \leq j \leq s \right. \right\}. $$
Teorema: Un finito gráfico de $H$ satisface (1) para todos los gráficos de $G$ si y sólo si $$\max_{x \in P_G} \sum_{i = 1}^n x_i = \alpha(H).$$
Entonces, mi pregunta es, sencillamente, este puede ser declarado mucho más simple (para alguien que no sabe mucho acerca de la programación lineal) en términos de algunas gráfico parámetro, es decir, es que un problema de programación lineal una forma de describir un conocido gráfico de parámetro? Puede el teorema de decir simplemente si y sólo si $\alpha(G) = \beta(G)$ para algunos gráfica del parámetro $\beta(G)$?
