Alladi Ramakrishnan Hall

How to store a graph?

Kshitij Gajjar

Indian Institute of Technology, Jodhpur

How does one store (save) a graph in a database? Typically, the vertices are labelled by a set: {1, 2, ..., n}. The edges can be denoted in many different ways: adjacency matrix, incidence matrix, and adjacency list, to name a few. However, what if the vertices are labelled in a more creative way, such that the labels themselves would denote the adjacencies of their vertices? This eliminates the need of storing the edges! This topic forms part of a heavily researched field called graph labelling, with connections to coding theory and information theory. In this talk we will be exploring a type of graph labelling called sum labelling. This is joint work with Henning Fernau (eccc.weizmann.ac.il/report/2021/114).