• ON AN UPPER BOUND FOR STRUCTURE GRACEFUL INDEX OF COMPLETE GRAPHS

Abstract

A graph structure G=(V,R₁,R₂,…,R_k) consists of a non-empty set V together with relations R₁,R₂,…,R_k on V which are mutually disjoint such that each R_i, 1≤i≤k, is symmetric and irreflexive.  If (u,v) ε R_i for some i, 1≤ i≤ k, we call it a R_i-edge and write it as uv. The structure graceful index of a graph G is defined as the minimum k for which G is k-structure graceful.  Let us denote it by SGI(G).  In our previous paper, we prove that the SGI(K_n)=2, for 4 < n < 11.  In this paper we obtain the upper bound for the SGI(K_n), for n > 10.