Prime labelings of infinite graphs

Kenigsberg, Matthew; Levin, Oscar

doi:10.2140/involve.2019.12.633

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

Prime labelings of infinite graphs

Matthew Kenigsberg and Oscar Levin

Vol. 12 (2019), No. 4, 633–646

DOI: 10.2140/involve.2019.12.633

Abstract

A finite graph on $n$ vertices has a prime labeling provided there is a way to label the vertices with the integers 1 through $n$ such that every pair of adjacent vertices has relatively prime labels. We extend the definition of prime labeling to infinite graphs and give a simple necessary and sufficient condition for an infinite graph to have a prime labeling. We then measure the complexity of prime labelings of infinite graphs using techniques from computability theory to verify that our condition is as simple as possible.

Keywords

graph labelings, infinite graphs, prime labelings, computability theory

Mathematical Subject Classification 2010

Primary: 05C78, 05C63, 05C85, 03D80

Milestones

Received: 22 February 2018

Revised: 9 July 2018

Accepted: 8 November 2018

Published: 16 April 2019

Communicated by Kenneth S. Berenhaut

Authors

Matthew Kenigsberg
Vanderbilt University Nashville, TN United States

Oscar Levin
School of Mathematical Sciences University of Northern Colorado Greeley, CO United States

Vol. 12, No. 4, 2019