Evaluating a permutation of the power and complement operations of a graph with respect to its independence numbers

Abstract

Let $G$ be a simple graph and $k\in \mathbb{N}$. Two important graph operations are: the $k$-th graph power of $G$, denoted by $G^k$, where $G^k$ is the graph obtained from $G$ by adding an edge between every pair of vertices that have a distance at most $k$, and the complement graph of $G$, denoted by $\overline{G}$. In this paper, we studied the relation between the independence numbers of ${\overline{G}}^k$ and $\overline{G^k}$.