2
$\begingroup$

Let $i(G)$ denote the number of independent sets of vertices of a graph $G$, write $G-v$ for the graph $G$ with the vertex $v$ removed, $G-H$ for the graph $G$ with the subgraph $H$ removed, and $N_k(v)$ for the subgraph of vertices at most distance $k$ from $v$ in $G$.

Define $h_G(v) = \frac{i(G)}{i(G-v)}-1 = \frac{i(G-N_1(v))}{i(G-v)}$.

Then $h_G(v)$ is the ratio of the number of independent sets of $G$ containing $v$ to the number of independent sets of $G$ that do not. Equivalently, Since every independent set containing $v$ is still an independent set if $v$ is removed, $h_G(v)$ is the proportion of independent sets of $G-v$ that are still independent if the vertex $v$ is added to them.

Intuitively, the presence of any vertex $u$ in $G$ adjacent to $v$ has the effect of decreasing $h_G(v)$, since it makes it more likely that an independent set of $G-v$ would not remain independent if $v$ were added. Conversely, any vertex $u$ that is distance 2 from $v$ would make it more likely that those vertices 1 away would not be included in an independent set, since every independent set containing $u$ could not contain any of the vertices adjacent to both $u$ and $v$. A vertex distance 3 away would make it less likely that a vertex distance 2 away is included and so on.

Is it true in general that $h_{G-u}(v) \leq h_G(v)$ if $d(u,v)$ is even, and $h_{G-u}(v) \geq h_G(v)$ if $d(u,v)$ is odd?

Or, in a somewhat weaker form, is it true that $h_{N_k(v)}(v) \leq h_G(v)$ if $k$ is even and $h_{N_k(v)}(v) \geq h_G(v)$ if $k$ is odd?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.