Uniform set labeling vertices to ensure adjacency coincides with disjointness

Abstract

Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. These sets may be finite or infinite (for example, in the case of geometric graphs). One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos et al. and they looked at minimising the underlying universal set necessary to represent any given graph and also showed that the problem is NP-complete. In this paper, we study a natural variant of this problem which is to consider graphs where vertices represent distinct as well as uniform cardinality sets and adjacency coincides with disjointness. Our motivation to look at disjointness instead of intersection is that several well-known graphs like the Petersen graph and Kneser graphs are expressed in the latter method. The parameters we take into account are: (1) UUSN the minimum universe size possible for obtaining uniform set labeling (2) ILN the smallest size of the largest label over all set labelings not necessarily uniform (where adjacency coincides with disjointness).