A213273 The smallest m such that the complete bipartite graph K_{n,n} has a coprime labeling using labels from {1,...,m}.

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

Author

Adam Berliner, Nate Dean, Jonelle Hook, Alison Marr, Aba Mbirika, Cayla McBee, Jun 08 2012

Keywords

• nonn

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).

Examples

			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}.
		

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, Coprime and Prime Labelings of Graphs, Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.8.
• 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.

Crossrefs

Cf. A213806, A284875, A291465.

Programs

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 *)

Extensions

More terms from Alois P. Heinz, Jun 16 2012

a(24) and beyond from Paul Tabatabai, Apr 29 2019