A284875 -id:A284875 - cp's OEIS frontend

A291465 a(n) is the least m >= n for which the complete bipartite graph K_{m,n} has a prime labeling.

1, 2, 4, 9, 14, 25, 36, 45, 52, 61, 62, 89, 90, 95, 98, 123, 140, 155, 162, 171, 172, 177, 216, 217, 226, 243, 244, 255, 264, 283, 318, 321, 340, 345, 374, 383, 384, 395, 400, 403, 422, 449, 456, 465, 478, 531, 546, 551, 552, 557, 562, 567, 594, 599, 604, 605

Offset: 1

Jonathan Sondow, Aug 24 2017

nonn

A prime labeling of K_{m,n} is a pair of sets A and B whose union is {1,2,...,m+n} such that |A| = m, |B| = n, and gcd(a,b) = 1 for all a in A and b in B. For an equivalent definition, the data above, and the formula below involving R_{n-1}, see Berliner, Dean, Hook, Marr, Mbirika (2016) Section 3.2.

			A = {1,3} and B = {2,4} is a prime labeling of K_{2,2}, so a(2) = 2.

Paul Tabatabai, Table of n, a(n) for n = 1..75
Adam H. Berliner, N. Dean, J. Hook, A. Marr, and A. Mbirika, Coprime and prime labelings of graphs, arXiv:1604.07698 [math.CO], 2016; Journal of Integer Sequences, Vol. 19 (2016), #16.5.8.

Cf. A104272, A213273, A213806, A284875.

n+1 <= a(n) <= R_{n-1} - n for n > 2, where R_{n-1} is a Ramanujan prime A104272.

a(14) onward from Paul Tabatabai, Apr 29 2019

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

Original entry on oeis.org

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

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

nonn

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

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

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.

Cf. A213806, A284875, A291465.

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

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

More terms from Alois P. Heinz, Jun 16 2012

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

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

Original entry on oeis.org

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

Alois P. Heinz, Jun 20 2012

nonn

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.

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

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

Cf. A213273, A284875, A291465.

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

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

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

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

cp's OEIS Frontend

A291465 a(n) is the least m >= n for which the complete bipartite graph K_{m,n} has a prime labeling.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions