Graph Labeling Problems
by
S. M. Hegde
Department of Mathematical and Computational Sciences, Karnataka Regional Engineering College, Surathkal, Srinivasnagar-574157, Karnataka, INDIA

Graph labelings, where the vertices are assigned real values or subsets of a set subject to certain conditions, have often been motivated by practical problems, but they are also of interest (logico-mathematical) in their own right. An enormous body of literature has grown around the subject.

Labeled graphs are becoming an increasingly useful family of Mathematical Models for a broad range of applications. They are useful in many Coding Theory problems, in determining ambiguities in X-Ray Crystallograpic analysis, to Design a Communication Network addressing System, in determining Optimal Circuit Layouts etc.

In this paper we study a labeling which uses the subsets of a set. Given a graph G and a nonempty set X, by a set assignment to the vertices of G we mean a function f: V(G) -> S, (where S is the power set of X) and given such a function we define the value g(uv) of an edge uv of G to be the symmetric difference of f(u) and f(v); We call f is a set indexer of G if both f and g are injective, and by a set indexed graph we mean a set indexable graph together with one of its set indexer. A set indexer f of a graph G is called a Segregation of X on G if f(G) and g(G) are disjoint families of subsets of X and if further, they form a partition of S then f is called a Set Sequential Labeling. A set indexer f is called a Set Graceful labeling, if g(G) = S.

In this paper we prove that if G has exactly one or two vertices of even degree or has ecactly three vertices of even degree with atleast two of them are joined or has exactly four vertices of even degree say, u, v, w, x such that uv wx are edges in G then G is not set sequential. Also we prove that if G has ecactly two or four vertices of odd degree as mentioned above then G is not set graceful. We prove that any graph can be embedded as an induced subgraph of a connected set sequential (or connected set graceful) graph, every tree can be embeded as an induced subgraph of a set sequential (set graceful) tree, etc.

Date received: November 6, 2001