Abstract: This paper proposed a improved KPPCT (IKPPCT,Improved Radix-k Planted Plane Cubic Tree) encoding scheme towards the problem of the lower data rate and the weak robustness of KPPCT encoding in dynamic graph watermarking.This scheme took advantage of uniqueness of binary tree's left-right branches to encode coefficient and expanded the range of watermarking value. And also it strengthened the ability to protect software by introducing the tamper-proofing to verify whether the watermarking structure was destroyed.Theoretical analysis and experimental results show that this scheme has high data rate and robustness,and is a better scheme.