login
A213273
The smallest m such that the complete bipartite graph K_{n,n} has a coprime labeling using labels from {1,...,m}.
4
2, 4, 7, 9, 11, 15, 17, 21, 23, 27, 29, 32, 37, 40, 43, 46, 49, 53, 57, 61, 63, 67, 71, 73, 77, 81, 83, 88, 92, 97, 100, 103, 107, 111, 113, 118, 122, 125, 128, 133, 135, 139, 143, 147, 149, 153, 157, 163, 165, 167, 171, 173, 178, 181, 188, 191, 194, 197, 202
OFFSET
1,1
COMMENTS
A prime labeling of a graph G is a labeling of the vertices with the integers 1, 2, ..., v (where v is the number of vertices) such that any two adjacent vertices have labels that are relatively prime. Here we are allowing the largest label m >= v and calling that a coprime labeling. Our goal is to find the smallest m that makes the labeling possible for K_{n,n} (which clearly does not have a prime labeling for n>2).
LINKS
Kevin Cuadrado, Table of n, a(n) for n = 1..2000 (terms 1..14 from Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika & C. McBee, terms 14..23 from Alois P. Heinz, terms 24..96 from Paul Tabatabai).
Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. McBee, Coprime and prime labelings of graphs, arXiv preprint arXiv:1604.07698 [math.CO], 2016.
Gary Chartrand, Cooroo Egan, and Ping Zhang, "Harmonious Labelings", How to Label a Graph (2019), Springer Briefs in Mathematics, Springer, Cham, 21-28.
Catherine Lee, Minimum coprime graph labelings, arXiv:1907.12670 [math.CO], 2019.
EXAMPLE
For n=12 and K_{12,12} the two independent sets would be labeled {1,3,5,9,15,17,19,23,25,27,29,31} and {2,4,7,8,11,13,14,16,22,26,28,32}.
MAPLE
b:= proc(n, k, t, s) option remember;
nops(s)>=t and (k>=t or n>1 and (b(n-1, k, t, s) or
b(n-1, k+1, t, select(x-> igcd(n, x)=1, s))))
end:
a:= proc(n) option remember; local m; forget(b);
for m from `if`(n=1, 1, a(n-1))
while not b(m, 1, n, {$2..m}) do od; m
end:
seq(a(n), n=1..14); # Alois P. Heinz, Jun 16 2012
MATHEMATICA
b[n_, k_, t_, s_] := b[n, k, t, s] = Length[s] >= t && (k >= t || n > 1 && (b[n - 1, k, t, s] || b[n - 1, k + 1, t, Select[s, GCD[n, #] == 1 &]]));
a[n_] := a[n] = Module[{m}, m = If[n == 1, 1, a[n - 1]]; While[!b[m, 1, n, Range[2, m]], m++]; m];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 23}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Adam Berliner, Nate Dean, Jonelle Hook, Alison Marr, Aba Mbirika, Cayla McBee, Jun 08 2012
EXTENSIONS
More terms from Alois P. Heinz, Jun 16 2012
a(24) and beyond from Paul Tabatabai, Apr 29 2019
STATUS
approved