## graphs with independence number = Shannon capacity

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.

-
So, have you ever answered any of your above questions? I am interested in all 3 separately. – Graphth Dec 8 at 16:32
One can also ask whether $\alpha(G)=\Theta(G)$ implies $\alpha(G)=\vartheta(G)$; if this is true, then the other conjectures immediately follow from the basic properties of the Lovász number $\vartheta$. Alas, we haven't been able to answer any of these four questions yet; but since our work lies mainly in relating these questions to problems in the mathematical foundations of quantum mechanics, we also haven't tried really hard. Our paper should be on the arXiv within a few days; I will announce it here. – Tobias Fritz Dec 8 at 17:32
$\alpha(G) = \Theta(G)$ does not imply $\alpha(G) = \vartheta(G)$. Haemers gives a counterexample in "An Upper Bound for the Shannon Capacity of a Graph". – Graphth Dec 10 at 18:46
By the way, did you know that if you do @Graphth before your response, then it will notify me of a response? I think since you wrote the question that it will notify you when I respond, even if I don't do @tobias – Graphth Dec 10 at 18:47
@Graphth: thanks a bunch, that's very helpful! We didn't know about that paper of Haemers. It will take us some time now to revise our paper now that we have this new information. Leave me a PM if we can use your real name in the acknowledgments. – Tobias Fritz Dec 12 at 18:22

@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.

-
 Ok, now I get it, thanks! That perfectly answers my side question. – Tobias Fritz Oct 5 at 16:48

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.

-