graphs with independence number = Shannon capacity - MathOverflow

graphs with independence number = Shannon capacity

2012-10-04T19:31:38Z

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 by Will Traves for graphs with independence number = Shannon capacity

2012-10-04T20:25:00Z

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.

Answer by Will Traves for graphs with independence number = Shannon capacity

2012-10-05T02:15:41Z

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