Divisor Orientations of Powers of Paths and Powers of Cycles

Abstract

In this paper, we prove that for any positive integers $k,n$ with $k\ge 2$ , the graph $P_k^n$ is a divisor graph if and only if $n\le 2k+2$ , where $P_n^k$ is the $k$ th power of the path $P_n$. For powers of cycles we show that $C_n^k$ is a divisor graph when $n\le 2k+2$, but is not a divisor graph when $n\ge 2k+2$,but is not a divisor graph when $n\ge 2k+\lfloor \frac{k}{2}\rceil ,$ where $C_n^k$ is the $k$th power of the cycle $C_n$. Moreover, for odd $n$ with $2k+2<n<2k+\lfloor \frac{k}{2}\rfloor +3$, we show that the graph $C_n^k$ is not a divisor graph.