login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A213806 Number of minimal coprime labelings for the complete bipartite graph K_{n,n}. 3
1, 1, 7, 3, 1, 3, 4, 5, 1, 9, 1, 1, 39, 2, 46, 16, 42, 68, 1, 175, 1, 5, 50 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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.

LINKS

Table of n, a(n) for n=1..23.

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

FORMULA

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

EXAMPLE

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

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

CROSSREFS

Cf. A213273, A284875, A291465.

Sequence in context: A078075 A067616 A199377 * A019856 A124603 A199722

Adjacent sequences:  A213803 A213804 A213805 * A213807 A213808 A213809

KEYWORD

nonn,more

AUTHOR

Alois P. Heinz, Jun 20 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 16:54 EDT 2019. Contains 324195 sequences. (Running on oeis4.)