most recent 30 from http://mathoverflow.net 2013-05-22T09:03:04Z http://mathoverflow.net/feeds/question/109489 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109489/making-a-graph-well-covered-without-changing-its-shannon-capacity Tobias Fritz 2012-10-12T20:17:00Z 2012-10-12T20:17:00Z

<p>This strongly relates to <a href="http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity" rel="nofollow">an earlier question</a> of mine.</p> <p>Let $G$ be a graph, $\alpha(G)$ its independence number and $\Theta(G)$ its Shannon capacity.</p> <p><strong>Question:</strong> can one 'add new vertices' to $G$ such that $G\subseteq G'$ becomes an induced subgraph of some <a href="http://en.wikipedia.org/wiki/Well-covered_graph" rel="nofollow">well-covered</a> $G'$ with $\alpha(G')=\alpha(G)$ and $\Theta(G') = \Theta(G)$?</p> <p>If so, this would be a way to 'uniformize' a graph without changing its Shannon capacity. Has anyone considered this question before?</p> <p>Thanks!</p>