Gracefulness of vertex duplicated complete bipartite graph for static and incremental frequency allocation

Abstract

We consider the vertex duplicated complete bipartite graph G(VA,VB)which is formed by duplicating all the vertices of a complete bipartite graph G(A,B). We then deal with the gracefulness of G(VA,VB) by considering both static and incremental frequency allocation to it. We have proved that the graceful labeling of G(VA,VB) is possible only for the case of static frequency allocation but not for the incremental frequency allocation. Finally we have shown that graceful labeling of G(A,B) satisfying certain additional properties can be extended to a σ-labeling of G(VA,VB) for the incremental frequency allocation.