A Comment on Dean's Construction of Prime Labelings on Ladders

arXiv2306.04088MaRDI QIDQ6439458FDOQ6439458

Authors: Stephen J. Curran, M. A. Ollis 

Publication date: 6 June 2023

Abstract: A prime labeling on a graph of order $m$ is an assignment of $1,2,ldots,m$ to the vertices of the graph such that each pair of adjacent vertices has coprime labels. The ladder of order $2n$ is the $2imesn$ grid graph graph $P_{2}imes{P}_n$. In a recent paper, Dean claimed a proof of the Prime Ladder Conjecture that every ladder has a prime labeling. We point out a flaw in Dean's construction, showing that a stronger hypothesis is needed for it to hold. We conjecture that this stronger hypothesis is true. We also offer an alternative construction inspired by Dean's approach which shows that if the Even Goldbach Conjecture and a particular strengthening of Lemoine's Conjecture are true then the Prime Ladder Conjecture follows.

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

This page was built for publication: A Comment on Dean's Construction of Prime Labelings on Ladders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439458)