A213806 -id:A213806 - 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

A284875 Values of m for which the complete bipartite graph K_{m,m} has a unique minimal coprime labeling.

Original entry on oeis.org

1, 2, 5, 9, 11, 12, 19, 21, 24, 47, 105, 109, 117, 118, 131, 132, 137, 144, 145, 146, 188, 189, 190, 191, 192, 194, 195, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 287, 288, 289, 290, 291, 310, 311, 312, 314, 315, 316, 317, 333, 341, 342, 343, 365

Offset: 1

Jonathan Sondow, May 14 2017

nonn

For definitions and examples, see A213273, A213806, and Berliner, Dean, Hook, Marr, Mbirika (2016) section 3.1.

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

Cf. A213273, A213806, A291465.

A213806(a(n)) = 1.

a(9) onwards 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

A284875 Values of m for which the complete bipartite graph K_{m,m} has a unique minimal coprime labeling.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions