graphs with independence number = Shannon capacity

Question

For $G$ a graph, let $\alpha(G)$ be its independence number and $\Theta(G)=\lim_n \sqrt[n]{\alpha(G^{\boxtimes})}$ its Shannon capacity, where $\boxtimes$ denotes strong product.

Consider graphs $G$ and $H$ satisfying $\alpha(G)=\Theta(G)$ and $\alpha(H)=\Theta(H)$. For example, $G$ and $H$ could be perfect, but the more interesting situations arise when neither of them is perfect.

Question: Does this assumption imply
(1) $\alpha(G\boxtimes H) = \alpha(G)\alpha(H)$ ?
(2) $\Theta(G\boxtimes H) = \Theta(G)\Theta(H)$ ?
(3) $\Theta(G + H) = \Theta(G) + \Theta(H)$ ?

Here, $G+H$ stands for the disjoint union of $G$ and $H$.

If my reasoning is correct, then (1) and (2) are equivalent and imply (3).

As far as I can see, neither the work of Haemers nor the results of Alon have anything directly to say about these questions. But then again, I am not an expert on this, so I might have missed something obvious.

Edit (see Will Traves' answer): Actually, I am specifically interested in those $G$ and $H$ which are well-covered.

Edit: The paper is here.

Answer 1

By now, we have been able to resolve this question, and our revised paper contains a proof showing that the answer to all three questions is negative in a very strong sense. Let me provide a brief summary here and refer to the paper for more details.

What we show is this: there exist graphs $G$ and $H$ with $\alpha(G)=\Theta(G)$ and $\alpha(H)=\vartheta(H)$ which violate all three desired inequalities. Note that the property $\alpha(H)=\vartheta(H)$ is even stronger than the required property $\alpha(H)=\Theta(H)$.

The construction crucially relies on the definitions and results on hypergraphs discussed in our paper and on results of Haemers. We have partially translated it into pure graph-theoretic terms, but it does not seem possible to do so completely.

The counterexample turns out to be the following:

• $G$ is a $108$-regular graph on $220$ vertices. The vertices correspond to the $3$-element subsets of $\{1,\ldots,12\}$ and two such vertices are adjacent whenever the subsets intersect in exactly one element. This graph was considered by Haemers, who showed that $\alpha(G) = \Theta(G) < \vartheta(G)$, and this property is the most important ingredient for us.

• $H$ is a graph constructed from the complement of $G$ which turns out to have $1131460$ vertices.

I suspect that a similar construction can be carried out starting with any graph $G$ having the property that $\alpha(G) = \Theta(G) < \vartheta(G)$, but we haven't checked all the details of this.

Answer 2

@Tobias: Sorry that my answer was not clear. According to Plummer http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf there are two equivalent definitions of well-covered graphs, one in terms of vertex covers and one in terms of independent sets.

A set of vertices $S$ is called a vertex cover if every vertex is either in $S$ or is adjacent to a vertex in $S$. The set $S$ is a minimum vertex cover if it is a vertex cover and no proper subset is a vertex cover. A set of vertices $T$ is called an independent set if no two vertices in $T$ are connected by an edge of the graph. A maximal independent set is one in which each vertex outside of $T$ is adjacent to some vertex in $T$. Note that if $V$ is the set of all vertices in the graph then $T$ is a maximal independent set if and only if $V \setminus T$ is a minimum vertex cover.

A graph is well-covered if all maximal independent sets have the same cardinality. Equivalently, a graph is well-covered if all minimum vertex covers have the same cardinality.

Of course, if $\bar{G}$ is the complementary graph to $G$ then a set of vertices forms a maximal clique in $\bar{G}$ precisely when the same set of vertices forms an independent set in $G$. So your condition that the "complements satisfy the additional property that all maximal cliques have the same size" means that the graphs themselves are well-covered. I don't see need for the additional requirement that every edge appears in some maximal clique - it seems to me that this always occurs.

You might find the paper by Philip Matchett helpful. It's emphasis is slightly different but it deals with operations on well-covered graphs. It can be found here: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45.

Answer 3

I believe that graphs in which all maximal cliques have the same size and every edge is contained in a maximal clique are called well-covered graphs. Sorry that I can't shed light on any of the serious questions that you raise.