Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$?

share|cite|improve this question
Just to clarify, is this something as simple as fractional chromatic number or something like that, i.e., is the condition $\alpha(H) = \chi_f(H)$? – Graphth Dec 15 '12 at 19:38
Should there be $s$ cliques in $G$, rather than $n$? – Mike Spivey Dec 15 '12 at 20:36
@MikeSpivey Yes, thanks. I fixed it. – Graphth Dec 15 '12 at 20:37
Given the way he's using it, $j$ must be a parameter, so I think he should really define $$P_{G,C} = \{(x_1, \ldots, x_n) \mid \forall i:x_i \geq 0 \wedge \sum_{g_i \in C} x_i \leq 1\}$$ where $C$ is a clique of $G$. – Peter Taylor Dec 15 '12 at 21:04
@PeterTaylor Did you notice $y_i^{(j)}$? Is that what you're talking about? – Graphth Dec 15 '12 at 21:08

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)$$

share|cite|improve this answer
I'll think about this more later, but that would fit in this situation since Shannon proved that the fractional chromatic number of the complement is an upper bound for the Shannon capacity. – Graphth Dec 15 '12 at 22:36
And, fractional clique number = fractional chromatic number. – Graphth Dec 15 '12 at 22:43
@Graphth, wow, thanks for the bounty! I was slightly surprised that the previous one wasn't awarded automatically, but it really wasn't necessary to do this. – Peter Taylor Feb 12 '13 at 23:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.