Graph theory is an area of mathematics that examines the structure and applications of graphs.  Unlike graphs in a calculus class, a graph arising in graph theory consists of a set of points, referred to as vertices, and edges.  Each edge connects a distinct pair of vertices.  A graph labeling is an assignment of values to the vertices or edges of a graph subject to certain constraints.  Many different graph labeling problems exist, our work will focus on prime labelings.

A prime labeling of a graph on k vertices is a labeling of the vertices by distinct integers 1, 2, 3, …, k in such a way that the labels of any two adjacent vertices are relatively prime.  Interest in prime labeling problems first began in the early 1980s when Entringer and Tout first conjectured that all trees are prime (A. Tout, 1982). Since then much work has been done trying to determine which classes of graphs are prime (Gallian, 2015).

Our CREU project seeks to use computing along with knowledge of graph theory to help determine for which values of n, Qn, the class of hypercube graphs, is prime.

Works Cited

  • Tout, A. D. (1982). Prime Labelings of Graphs. National Academy Science Letters, 11, 365 – 368.
  • Gallian, J. A. (2015). A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, DS6.