Distance Independent Domination in Iterated Line Graphs

Abstract

Let $k\ge 1$ be an integer and let $G=(V,E)$ be a graph. A set $S$ of vertices of $G$ is $k$-independent if the distance between any two vertices of $S$ is at least $k+1$. We denote by ${\rho }_k(G)$ the maximum cardinality among all $k$-independent sets of $G$. Number ${\rho }_k(G)$ is called the $k$-packing number of $G$. Furthermore, $S$ is defined to be $k$-dominating set in $G$ if every vertex in $V(G)–S$ is at distance at most $k$ from some vertex in $S$. A set $S$ is $k$-independent dominating if it is both $k$-independent and $k$-dominating. The $k$-independent dominating number, $i_k(G)$, is the minimum cardinality among all $k$-independent dominating sets of $G$. We find the values $i_k(G)$ and ${\rho }_k(G)$ for iterated line graphs.