Set-Valued Graphs: A Survey
Publication Type:Journal Article
Source:Journal of Discrete Mathematical Sciences and Cryptography, Volume 18, Number 1-2, p.55-80 (2015)
The problem of set valuation of a graph requires both the vertices and edges of an undirected simple graph G to be labeled with subsets of a nonempty set. The label of an edge uv of G is obtained as the symmetric difference of the subsets assigned to the vertices u and v of G. A graph G is said to be set-valued if there exists an assignment of subsets of a nonempty set on the vertices of G such that the following two conditions holds:(i) all the subsets on the vertices are distinct and, (ii) all the subsets on the edges are distinct. The objective of this article is to organize and summarize much of the work done on set-valued graphs since its inception in 1983. Many open problems and conjectures are included. We explore new directions with regards to the enumeration of set-valued graphs.