×

Proof of the prime ladder conjecture. (English) Zbl 1414.05254

Summary: A prime labeling of a graph \(G = (V, E)\) is a labeling of the vertices with the numbers \(1, 2, \dots , |V |\) where each vertex gets a unique label and, for each edge \(uv\), the labels for \(u\) an \(v\) are relatively prime. A graph is called prime if it has a prime labeling. The ladder conjecture states that every ladder \(P_n\times P_2\) is prime. We prove this conjecture. The following result which is essential to the proof of this conjecture may be of independent interest as it relates to the celebrated Goldbach conjecture. Define a canonical partition of an integer \(n\) as a representation of n as the sum ofP odd primes \(p_1, p_2,\dots, pm\), where \(p_j\ge 2\sum^{j-1}_{i=1}p_i+ 3\) for all \(j\in \{2, 3,\dots , m\}\). Every integer \(n\ge 50\) has a canonical partition.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05A17 Combinatorial aspects of partitions of integers
PDFBibTeX XMLCite
Full Text: Link

References:

[1] J. B. Babujee and L. Shobana, Prime and prime cordial labeling, Int. J. Contemp. Math. Sciences 5(47) (2010), 2347-2356. · Zbl 1217.05199
[2] A. H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. D. McBee, Coprime and prime labelings of graphs, J. Integer Seq. 19 (2016), Article 17.5.8, 1-14. · Zbl 1342.05127
[3] H.-L. Fu and K.-C. Huang, On prime labellings, Discrete Math. 127 (1994), 181-186. · Zbl 0802.05064
[4] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. DS6 (2014). · Zbl 0953.05067
[5] P. Haxell, O. Pikhurko and A. Taraz, Primality of trees, J. Comb. 2(4) (2011), 481-500. · Zbl 1269.05096
[6] A. V. Kanetkar, Prime labeling of grids, AKCE Int. J. Graphs Combin. 6 (2009), 135-142. · Zbl 1210.05147
[7] A. Loo, On the primes in the interval [3n, 4n], Int. J. Contemp. Math. Sciences 6(38) (2011), 1871-1882. · Zbl 1267.11006
[8] M. Sundaram, R. Ponraj, and S. Somasundaram, A note on prime labeling of ladders, Acta Ciencia Indica. 33 (2007), 471-477. · Zbl 1139.05061
[9] V. Vilfered, S. Somasundaram and T. Nicholas, Classes of prime labelled graphs, Int. J. of Management and Systems 18(2) (2002), 217-226.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.