The independent subsets of powers of paths and cycles

For a graph $G$ we denote by $V(G)$ the set of its vertices, and by $E(G)$ the set of its edges. For $n, h\geq0$, (i) the $h$-power of a path, denoted by $P_{n}^{(h)}$ is a graph with $n$ vertices $v_{1}, v_{2}, ..., v_{n}$ such that, for $1\leq i,j\leq n$, $(v_i,v_j)\in E(P_{n}^{(h)})$ if and only if $|j-i|\leq h$; (ii) the $h$-power of a cycle, denoted by $Q_{n}^{(h)}$ is a graph with $n$ vertices $v_{1}, v_{2}, ..., v_{n}$ such that, for $1\leq i,j \leq n$, $(v_i,v_j)\in E(Q_{n}^{(h)})$ if and only if $|j-i|\leq h$ or $|j-i|\geq n-h$. Thus, for instance, $P_{n}^{(0)}$ and $Q_{n}^{(0)}$ are the graphs made of $n$ isolated nodes, $P_{n}^{(1)}$ is the path with $n$ vertices, and $Q_{n}^{(1)}$ is the cycle with $n$ vertices. The following definition introduces the key notion in this work. An independent subset $S$ of a graph $G$ is a subset of $V(G)$ not containing adjacent vertices. In the first part of our work we deal with the independent subsets of $P_{n}^{(h)}$. We evaluate $p_n^{(h)}$, i.e. the number of independent subsets of $P_{n}^{(h)}$, and $H_n^{(h)}$, i.e. the number of edges of the Hasse diagram of the poset of independent subsets of $P_{n}^{(h)}$ ordered by inclusion. Our main result is that, for $n, h\geq 0$, the sequence $H_n^{(h)}$ is the convolution of the sequence $p_n^{(h)}$ with itself. In the second part, we derive similar results for the number of edges of the Hasse diagram of the poset of independent subsets of $Q_{n}^{(h)}$. If time allows, we discuss some bijections connecting our independent subsets with certain compositions of an integer.