|
|||||
 |
|
|
|
|
|
|
|
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 vertices has a prime labeling provided there is a way to label the vertices with the integers 1 through 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. |
PDF Access Denied
We have not been able to recognize your IP address
18.222.148.124
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for USD 30.00:
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 |
|
