A clique-difference encoding scheme for labelled kk-path graphs

We present in this paper a codeword for labelled kk-path graphs. Structural properties of this codeword are investigated, leading to the solution of two important problems: determining the exact number of labelled kk-path graphs with nn vertices and locating a hamiltonian path in a given kk-path graph in time O(n)O(n). The corresponding encoding scheme is also presented, providing linear-time algorithms for encoding and decoding.