login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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
Sequence in context: A081841 A299234 A366462 * A027904 A193600 A190429
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 10:59 EDT 2024. Contains 371277 sequences. (Running on oeis4.)