Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
The new one added vertex should be adjacency with each vertex which can be in a maximum independent set at least. –  Eden Harder Mar 25 at 1:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.