Further Results on Set Sequential and Set Graceful Graphs

Abstract

Unless mentioned otherwise, we consider only finite simple graphs and for all notations in Graph theory we follow Harary [4]. Several practical problems in real life situations have motivated the study of labeling the vertices and edges of a graph G = (V, E) which are required to obey a variety of conditions depending on the structure of G such as adjacency. There is an enormous amount of literature built up on several kinds of labelings of graphs over the last three decades or so. An interested reader can refer to Gallian [3]. Acharya [1] has initiated a general study of the labelings of the vertices and edges of a graph using subsets of a set and indicated their potential applications in a variety of other areas of human enquiry. An assignment f of distinct subsets (nonempty subsets) of a finiteset X to the vertices of a given graph G = (V, E) so that the values of the edges e = uv are obtained as the symmetric differences of the sets assigned to the vertices u and v such that both, the vertex function as well as the edge functions are injective, is called a set indexer of G. A set indexer f is called a set graceful labeling, if all the nonempty subsets of X are obtained on the edges. A set indexer / is called a set sequential labeling if the sets on the vertices and edges together form the set of all nonempty subsets of X. A graph is called set graceful (set sequential) if it admits a set graceful (set sequential) labeling with respect to a set X. 2005 Elsevier Ltd. All rights reserved.