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 \geq 2\) , the graph \(P_k^n\) is a divisor graph if and only if \(n \leq 2k + 2\) , where \(P^k_n\) is the \(k\) th power of the path \(P_n\). For powers of cycles we show that \(C^k_n\) is a divisor graph when \(n \leq 2k + 2\), but is not a divisor graph when \(n \geq 2k + 2\),but is not a divisor graph when \(n\geq 2k+\lfloor \frac{k}{2}\rceil,\) where \(C^k_n\) 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^k_n\) is not a divisor graph.