In relay cellular network, relay links will consume extra frequency resources, which makes radio resource allocation become more complex and important. A new frequency allocation scheme is proposed to increase cell capacity and improve signal-to-interference ratio (SIR) of users located at cell edges. By dividing cell into different parts and configuring each of these parts with a unique reuse factor, this scheme improves spectral utilization efficiency and avoids inter-cell interference effectively. Optimal combinations of reuse factors and locations of relay nodes are also addressed and investigated. Computer simulation results show that, by employing the proposed scheme, maximum cell capacity gains of about 50%, 35% and 30% can be achieved in comparison with conventional cellular network scheme, traditional reuse partitioning scheme and reuse-adjacent-cell-frequencies scheme, respectively. Moreover, since in the proposed scheme resources are dynamically allocated among relay nodes, more benefits can be obtained in comparison with fixed resource allocation schemes under non-uniform traffic distribution.