4

2

This strongly relates to an earlier question of mine.

Let $G$ be a graph, $\alpha(G)$ its independence number and $\Theta(G)$ its Shannon capacity.

Question: can one 'add new vertices' to $G$ such that $G\subseteq G'$ becomes an induced subgraph of some well-covered $G'$ with $\alpha(G')=\alpha(G)$ and $\Theta(G') = \Theta(G)$?

If so, this would be a way to 'uniformize' a graph without changing its Shannon capacity. Has anyone considered this question before?

Thanks!

flag

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.