The space complexity of sum labelling (Q6056630)

The paper entitled The Space Complexity of Sum Labeling is very interesting. This paper discusses the sum graph which is a graph that can be labelled by distinct positive integers so that there is an edge between two vertices if and only if the sum of the two vertices of the edge is a label of another vertex in the graph. Obviously, the graph always has at least one isolated vertex. The minimal number of isolated vertices that are needed is called the sum number. The paper uses a different approach compared with other papers on sum graphs for several families of graphs. The authors obtain an algorithm to label the graph so that it is a sum graph in polynomial time. They also discuss the use of the sum graph concept to store the graph efficiently. In this paper, they also provide the bounds on how big is the graph storage needed. They also study the possibility of storing graphs using sum graphs in databases. They close the paper by giving some open problems.