Prime labelings of generalized Petersen graphs

Schluchter, Steven A.; Schroeder, Justin Z.; Cokus, Kathryn; Ellingson, Ryan; Harris, Hayley; Rarity, Ethan; Wilson, Thomas

doi:10.2140/involve.2017.10.109

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Prime labelings of generalized Petersen graphs

Steven A. Schluchter, Justin Z. Schroeder, Kathryn Cokus, Ryan Ellingson, Hayley Harris, Ethan Rarity and Thomas Wilson

Vol. 10 (2017), No. 1, 109–124

DOI: 10.2140/involve.2017.10.109

Abstract

A graph $G$ is called prime if the vertices of $G$ can be assigned distinct labels $1, 2, \dots, | V (G) |$ such that the labels on any two adjacent vertices are relatively prime. By showing that for every even $n \leq 2.468 \times 1 0^{9}$ there exists $s \in [1, n - 1]$ such that both $n + s$ and $2 n + s$ are prime, we prove the generalized Peterson graph $P (n, 1)$ is prime for all even $n \in [4, 2.468 \times 1 0^{9}]$ . Moreover, for a fixed $n$ we describe a method for labeling $P (n, k)$ that is a prime labeling for multiple values of $k$ . Using this method, we prove $P (n, k)$ is prime for all even $n \leq 50$ and all odd $k \in [1, n ∕ 2)$ .

Keywords

graph labeling, generalized Petersen graph, prime graph

Mathematical Subject Classification 2010

Primary: 05C78

Milestones

Received: 8 September 2015

Revised: 20 November 2015

Accepted: 28 November 2015

Published: 11 October 2016

Communicated by Joseph A. Gallian

Authors

Steven A. Schluchter
Department of Mathematical Sciences George Mason University 4400 University Drive MS: 3F2 Fairfax, VA 22030 United States

Justin Z. Schroeder
Mosaic Centre Radstock Kej Bratstvo Edinstvo 45 1230 Gostivar Macedonia

Kathryn Cokus
George Mason University 4400 University Drive Fairfax, VA 22030 United States

Ryan Ellingson
George Mason University 4400 University Drive Fairfax, VA 22030 United States

Hayley Harris
George Mason University 4400 University Drive Fairfax, VA 22030 United States

Ethan Rarity
George Mason University 4400 University Drive Fairfax, VA 22030 United States

Thomas Wilson
George Mason University 4400 University Drive Fairfax, VA 22030 United States

Vol. 10, No. 1, 2017