[Math] graph theory interpretation of this linear programming problem

graph theorylinear programming

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy
$$\alpha(G \boxtimes H) = \alpha(G) \alpha(H) \qquad (1)$$
for all graphs $G$. Here, $\alpha$ represents the independence number, and $\boxtimes$ represents the strong product. But, he does it in terms of linear programming which I am not great at. So, I'm wondering if what he did corresponds to some known graph parameter. Below I transcribe the relevant portion of the paper for completion.

Let $G$ be a finite graph. $V(G) = \{g_1, \ldots, g_n\}$. Let $\{C_1, \cdots, C_s\}$ be a fixed ordering of all the different cliques of $G$. Define $y_i^{(j)}$ to be 1 exactly when $g_i \in C_j$, and 0 otherwise. Also, let
$$
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\}.
$$

Theorem: A finite graph $H$ satisfies (1) for all graphs $G$ if and only if
$$\max_{x \in P_G} \sum_{i = 1}^n x_i = \alpha(H).$$

So, my question is simply, can this be stated much simpler (to someone who doesn't know much about linear programming) in terms of some graph parameter, i.e., is that linear programming problem a way of describing a known graph parameter? Can the theorem simply say if and only if $\alpha(G) = \beta(G)$ for some graph parameter $\beta(G)$?

Best Answer

If I'm correctly interpreting the notation then it's a kind of dual of the fractional clique number: more precisely, it's the fractional clique number of the complement graph. Since the fractional clique number is equal to the fractional chromatic number (see ref.), it's also the fractional chromatic number of the complement graph.

For graph $G = (V, E)$, let

  • $C$ be the set of cliques of $G$
  • $I$ be the set of independent sets of $G$
  • $W$ be the set of non-negative vertex weight functions $\{w : V \rightarrow \mathbb{R}^+\}$

Then the parameter of interest is $$\beta(G) = \max_{w \in W} \left[\forall c \in C : \sum_{v \in c} w(v) \leq 1\right] \sum_{v \in V} w(v)$$

The fractional clique number is $$\omega^*(G) = \max_{w \in W} \left[\forall i \in I : \sum_{v \in i} w(v) \leq 1 \right] \sum_{v \in V} w(v)$$

Related Question