##
Encoding of Graphs

Darren A. Narayan

Department of Mathematics and Statistics

Rochester Institute of Technology

dansma@rit.edu
### ABSTRACT

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.