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

  • 0
    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)$?2012-12-15
  • 1
    Should there be $s$ cliques in $G$, rather than $n$?2012-12-15
  • 0
    @MikeSpivey Yes, thanks. I fixed it.2012-12-15
  • 0
    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$.2012-12-15
  • 0
    @PeterTaylor Did you notice $y_i^{(j)}$? Is that what you're talking about?2012-12-15
  • 0
    He uses $j$ in $y_i^{(j)}$ (or $[g_i \in C_j]$, using an Iverson bracket), and he constrains its value to be between 1 and $s$ inclusive, but he doesn't bind it as a parameter of anything. An alternative to my previous comment is to add an existential quantifier and define $$P_G = \{(x_1, \ldots, x_n) \mid \exists j : \sum_{i = 1}^n [g_i \in C_j] x_i \leq 1 \wedge \forall i : x_i \geq 0 \wedge 1 \leq j \leq s\}$$2012-12-15
  • 0
    I'm afraid that the answer is “no”. The parameter $\min_x \sum_i x_i$ doesn't have a simple combinatorial interpretation. Note that this quantity is not necessarily integer (for example, it is equal to $5/2$ in a cycle of length $5$). The fact that a parameter is not integer often indicates that there is no simple combinatorial definition for it.2012-12-15
  • 0
    Actually on further thought I think it should be a universal quantifier rather than an existential one.2012-12-15
  • 0
    @Yury The fractional chromatic number of the 5-cycle is 5/2. And, my comment right after the question asks if perhaps this is the fractional chromatic number.2012-12-15
  • 0
    @Graphth: I didn't see your comment. Yes, this quantity is equal to the *fractional chromatic number of the complement of $G$*. (It is also known as the *fractional clique cover number*.)2012-12-15

1 Answers 1