Encoding of Graphs

Darren A. Narayan
Department of Mathematics and Statistics
Rochester Institute of Technology


We will investigate the following problem from graph theory: A finite graph G is said to have a representation modulo n, if its vertices can be labelled with distinct integers between 0 and n-1 inclusive so that two vertices are connected by an edge if and only if the difference between their labels is relatively prime to n. For a given graph G we will seek the smallest n such that G has a representation modulo n.

We will present some results from [1] including a new connection between this problem and the existence of families of mutually orthogonal Latin squares. In addition, we will consider running times of potential computer simulations and algorithms needed to solve the posed problem.

[1] A. B. Evans, G. Isaak, D. A. Narayan, Representations of Graphs Modulo n, Discrete Mathematics, 223 (2000) 109-123.

Colloquia Series page.