graphs with independence number = Shannon capacity - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:48:27Z http://mathoverflow.net/feeds/question/108851 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity graphs with independence number = Shannon capacity Tobias Fritz 2012-10-04T19:31:38Z 2012-12-18T08:31:34Z <p>For $G$ a graph, let $\alpha(G)$ be its independence number and $\Theta(G)=\lim_n \sqrt[n]{\alpha(G^{\boxtimes})}$ its <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Shannon_capacity_of_a_graph" rel="nofollow">Shannon capacity</a>, where $\boxtimes$ denotes <a href="http://en.wikipedia.org/wiki/Strong_graph_product" rel="nofollow">strong product</a>.</p> <p>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.</p> <p><strong>Question:</strong> Does this assumption imply<br> (1) $\alpha(G\boxtimes H) = \alpha(G)\alpha(H)$ ?<br> (2) $\Theta(G\boxtimes H) = \Theta(G)\Theta(H)$ ?<br> (3) $\Theta(G + H) = \Theta(G) + \Theta(H)$ ? </p> <p>Here, $G+H$ stands for the disjoint union of $G$ and $H$.</p> <p>If my reasoning is correct, then (1) and (2) are equivalent and imply (3).</p> <p>As far as I can see, neither the work of <a href="http://ieeexplore.ieee.org/xpl/login.jsp?tp=&amp;arnumber=1056027&amp;url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1056027" rel="nofollow">Haemers</a> nor the results of <a href="http://www.cs.umd.edu/~gasarch/const_ramsey/alon98.pdf" rel="nofollow">Alon</a> 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.</p> <p><em>Edit</em> (see Will Traves' answer): Actually, I am specifically interested in those $G$ and $H$ which are <a href="http://en.wikipedia.org/wiki/Well-covered_graph" rel="nofollow">well-covered</a>.</p> <p><em>Edit</em>: The paper is <a href="http://arxiv.org/abs/1212.4084" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity/108857#108857 Answer by Will Traves for graphs with independence number = Shannon capacity Will Traves 2012-10-04T20:25:00Z 2012-10-04T20:25:00Z <p>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. </p> http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity/108882#108882 Answer by Will Traves for graphs with independence number = Shannon capacity Will Traves 2012-10-05T02:15:41Z 2012-10-05T02:15:41Z <p>@Tobias: Sorry that my answer was not clear. According to Plummer <a href="http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf" rel="nofollow">http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf</a> there are two equivalent definitions of well-covered graphs, one in terms of vertex covers and one in terms of independent sets. </p> <p>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. </p> <p>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.</p> <p>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. </p> <p>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: <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45" rel="nofollow">http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45</a>. </p>