The $k$-independent graph of a graph

Abstract

Let $G=(V,E)$ be a simple graph. A set $I\subseteq V$ is an independent set, if no two of its members are adjacent in $G$. The $k$-independent graph of $G$, $I_k(G)$, is defined to be the graph whose vertices correspond to the independent sets of $G$ that have cardinality at most $k$. Two vertices in $I_k(G)$ are adjacent if and only if the corresponding independent sets of $G$ differ by either adding or deleting a single vertex. In this paper, we obtain some properties of $I_k(G)$ and compute it for some graphs.

10 pages, 4 Figures......This is updated version of paper in arXiv:1510.05360 which the name of co-author "Abdul Jalil M. Khalaf" added