Atlantic Graph Theory Seminar: Sebastian Cioaba, University of Delaware

Addressing graphs and hypergraphs

In 1970s, Ron Graham and Henry Pollak introduced the notion of graph addressing which is a labeling of the vertices of an undirected graph by words of the same length over the alphabet {0,1,*} such that the distance between any two vertices equals the number of positions in their labels/addresses where one vertex has a 0 and the other one has a 1. The minimum of length of such words has been investigated by various people and is closely related to the partition of the edge set of the graph into bicliques (complete bipartite subgraphs). In this talk, I will describe some recent results related to this parameter for various families of graphs and the corresponding problem for hypergraphs.