2
$\begingroup$

Suppose $\alpha(G)\leq\alpha(H)$ where $G$ and $H$ are graphs, and $\alpha(.)$ is the independence number of graph. Is the following statement true?

$\alpha(G\boxtimes G) \leq \alpha(H\boxtimes H)$ where $\boxtimes$ is the strong product of two graphs.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

This is false.

Let $G$ be with edges $ [(0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)] $

and $H$ with edges $[(0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)] $.

$\alpha(G)=\alpha(H)=2$.

$\alpha(G\boxtimes G)=5,\alpha(H\boxtimes H)=4$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there any example in which $\alpha(G)<\alpha(H)$ but $\alpha(G\boxtimes G)\geq\alpha(H\boxtimes H)$? $\endgroup$
    – Math_Y
    Commented Mar 5, 2015 at 10:10
  • $\begingroup$ @MohammadMahdi haven't found any so far... $\endgroup$
    – joro
    Commented Mar 5, 2015 at 10:41
6
$\begingroup$

Surely no. Instead of specific example, let me give general speculations. If this were true, then $\alpha(G)=\alpha(H)$ would imply $\alpha(G\boxtimes G)=\alpha(H\boxtimes H)$, and hence for all strong powers, making Shannon capacity the function of independence number. But SC does not depend only on independence number.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there graph classes where equality for powers hold? $\endgroup$
    – joro
    Commented Mar 5, 2015 at 10:14
  • $\begingroup$ @joro: Perfect graphs. $\endgroup$
    – Math_Y
    Commented Mar 5, 2015 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .