A213806 Number of minimal coprime labelings for the complete bipartite graph K_{n,n}.

1, 1, 7, 3, 1, 3, 4, 5, 1, 9, 1, 1, 39, 2, 46, 16, 42, 68, 1, 175, 1, 5, 50, 1, 627, 1256, 1177, 10, 1860, 7144, 15, 170, 27156, 178, 64, 2, 6335, 6334, 15592, 4522, 3230, 113926, 99010, 72256, 114606, 199042, 1, 198518, 151036, 236203, 8557, 26542, 21388

Offset: 1

Author

Alois P. Heinz, Jun 20 2012

Keywords

• nonn

Comments

A minimal coprime labeling for K_{n,n} uses two disjoint n-subsets of {1,...,m} with minimal m = A213273(n) >= 2*n as labels for the two disjoint vertex sets such that labels of adjacent vertices are relatively prime. One of the label sets contains m.

Examples

			a(1) = 1: the two label sets are {{1}, {2}} with m=2.
a(2) = 1: {{1,3}, {2,4}} with m=4.
a(3) = 7: {{2,4,5}, {1,3,7}}, {{1,3,5}, {2,4,7}}, {{2,3,4}, {1,5,7}}, {{2,3,6}, {1,5,7}}, {{2,4,6}, {1,5,7}}, {{3,4,6}, {1,5,7}}, {{1,2,4}, {3,5,7}}.
a(4) = 3: {{2,4,7,8}, {1,3,5,9}}, {{2,4,5,8}, {1,3,7,9}}, {{1,2,4,8}, {3,5,7,9}}.
a(5) = 1: {{2,4,5,8,10}, {1,3,7,9,11}}.
a(21) = 1: {{2,4,5,8,10,11,16,20,22,23,25,29,31,32,40,44,46,50,55,58,62}, {1,3,7,9,13,17,19,21,27,37,39,41,43,47,49,51,53,57,59,61,63}}.
		

Links

• Kevin Cuadrado, Table of n, a(n) for n = 1..105
• Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, C. McBee, Coprime and prime labelings of graphs, arXiv preprint arXiv:1604.07698 [math.CO], 2016.
• Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Crossrefs

Cf. A213273, A284875, A291465.

Programs

Maple

b:= proc(n, k, t, s) option remember;
      `if`(nops(s)>=t and k>=t, binomial(nops(s), t),
      `if`(n<1, 0, b(n-1, k, t, s)+ b(n-1, k+1, t,
      select(x-> x<>n and igcd(n, x)=1, s))))
    end:
g:= proc(n) option remember; local m, r;
      for m from `if`(n=1, 2, g(n-1)[1]) do
        r:= b(m-1, 1, n, select(x-> igcd(m, x)=1, {$1..m-1}));
        if r>0 then break fi
      od; [m, r]
    end:
a:= n-> g(n)[2]:
seq(a(n), n=1..11);

Mathematica

b[n_, k_, t_, s_] := b[n, k, t, s] = If[Length[s] >= t && k >= t, Binomial[Length[s], t], If[n < 1, 0, b[n - 1, k, t, s] + b[n - 1, k + 1, t, Select[s, # != n && GCD[n, #] == 1 &]]]];
g[n_] := g[n] = Module[{m, r}, For[ m = If[n == 1, 2, g[n - 1][[1]] ], True, m++, r = b[m - 1, 1, n, Select[Range[1, m - 1], GCD[m, #] == 1 &]]; If [r > 0,  Break[]]]; {m, r}];
a[n_] := a[n] = g[n][[2]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 18}] (* Jean-François Alcover, Nov 08 2017, after Alois P. Heinz *)

Formula

a(A284875(n)) = 1. - Jonathan Sondow, May 21 2017

Extensions

Terms a(24) and beyond from Kevin Cuadrado, Dec 01 2020