7
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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)$? $\endgroup$
    – GeoffDS
    Dec 15, 2012 at 19:38
  • 1
    $\begingroup$ Should there be $s$ cliques in $G$, rather than $n$? $\endgroup$
    – Mike Spivey
    Dec 15, 2012 at 20:36
  • $\begingroup$ @MikeSpivey Yes, thanks. I fixed it. $\endgroup$
    – GeoffDS
    Dec 15, 2012 at 20:37
  • $\begingroup$ 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$. $\endgroup$
    – Peter Taylor
    Dec 15, 2012 at 21:04
  • $\begingroup$ @PeterTaylor Did you notice $y_i^{(j)}$? Is that what you're talking about? $\endgroup$
    – GeoffDS
    Dec 15, 2012 at 21:08

1 Answer 1

Reset to default
2
+500
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – GeoffDS
    Dec 15, 2012 at 22:36
  • 1
    $\begingroup$ And, fractional clique number = fractional chromatic number. $\endgroup$
    – GeoffDS
    Dec 15, 2012 at 22:43
  • $\begingroup$ @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. $\endgroup$
    – Peter Taylor
    Feb 12, 2013 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .