DMS Combinatorics Seminar

Speaker: Aleyah Dawkins (Carnegie Mellon University)

Title: The radio number of Moore graphs, cages, and random graphs

Abstract: The study of radio labelings is motivated by the frequency assignment problem, a central challenge in wireless and satellite communication, which addresses assigning frequencies to a network of transmitters so that those located near each other do not have signal interference. Chartrand, Erwin, Harary, and Zhang were the first to model this problem using graphs, where each vertex represents a transmitter and edges reflect proximity. Given a graph, a radio labeling is a mapping that assigns each vertex to a positive integer such that vertices closer in distance have more widely separated labels. In particular, for any pair of vertices, the difference between the labels plus the distance between the vertices must be at least one more than the diameter of the graph. The minimum number of labels needed for any radio labeling is called the radio number. In this talk, we discuss results on the radio number for graph families closely related to Moore bounds, including Moore graphs, bipartite Moore graphs, and cages. These are highly symmetric, low diameter networks that approach extremal bounds on the possible number of vertices, making them ideal to consider for efficient labeling. We go on to investigate the behavior of radio number of random graphs, offering insights into large-scale network behavior.