Set labeling of graphs

Abstract

Given a universal set and its subsets, intersection graph can be characterized as the graph with one distinct subset of given universal set for each vertex of the graph and any two non-adjacent vertices have no element common in their respective set. This was first studied by Erdos. For Kneser graph and Petersen graph, adjacency is characterized by disjointness. This motivates us to look at disjointness instead of intersection. This report contains results about asymptotic bounds for valid labeling of some special classes of graphs such as harary graphs, split graphs, bipartite graphs, disjoint complete graphs and complete multipartite graphs. Parameters relevant to study of labeling of vertices of the graphs are minimum label size possible (ILN), minimum universe size possible (USN) and their uniform versions such as UILN and UUSN. We have also proposed one framework to label disconnected graphs.