login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A245239 Maximum frustration of complete bipartite graph K(n,6). 5
0, 3, 4, 7, 9, 11, 13, 16, 17, 19, 21, 24, 25, 28, 29, 32, 33, 36, 37, 40, 42, 45, 46, 48, 50, 53, 54, 57, 58, 61, 63, 66, 66, 69, 70, 73, 75, 78, 79, 82, 83, 85, 87, 90, 91, 94, 95, 98, 99, 102, 103, 106, 108, 111, 112, 114, 116, 119, 120, 123, 124, 127, 129 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The maximum frustration of a graph is the maximum cardinality of a set of edges that contains at most half the edges of any cut-set.  Another term that is used is "line index of imbalance". It is also equal to the covering radius of the coset code of the graph.

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

G. S. Bowlin, Maximum Frustration in Bipartite Signed Graphs, Electr. J. Comb. 19(4) (2012) #P10.

R. L. Graham and N. J. A. Sloane, On the Covering Radius of Codes, IEEE Trans. Inform. Theory, IT-31(1985), 263-290

P. Solé and T. Zaslavsky, A Coding Approach to Signed Graphs, SIAM J. Discr. Math 7 (1994), 544-553

FORMULA

a(n) = floor(66/32*n) - 1 if n=6 or n == 5 mod 8 or n == 2,4,7,9 or 11 mod 16 or n == 10,15,16 or 24 mod 32;  a(n) = floor(66/32*n) - 2 if n == 1, 3, 17 or 19 mod 32, and floor(66/32*n) otherwise.

a(n+32) = a(n) + 66 except for n = 5.

a(n) = A245230(max(n,6), min(n,6)).

Empirical g.f.: -x^2*(x^35 -x^34 -x^33 +x^32 +x^31 -x^30 -x^29 -2*x^28 -x^27 -x^26 -2*x^24 -x^23 -x^22 -x^21 -x^20 -2*x^18 -2*x^17 -x^16 +x^15 -2*x^14 -2*x^13 -x^12 +x^11 -2*x^10 -2*x^9 -x^8 -x^6 -x^5 -2*x^4 -x^3 -x -3) / ((x -1)^2*(x +1)*(x^4 +1)*(x^8 +1)*(x^16 +1)). - Colin Barker, Sep 22 2014

EXAMPLE

For n=2 a set of edges that achieves the maximum cardinality a(2) = 3 is {(1,3),(1,4),(1,5)}.

MAPLE

A245239:= n -> floor(66/32*n) - piecewise(n=6 or (n mod 8 = 5) or member(n mod 16, {2, 4, 7, 9, 11}) or member(n mod 32, {10, 15, 16, 24}), 1, member(n mod 32, {1, 3, 17, 19}), 2, 0): seq(A245239(n), n=1..30);

MATHEMATICA

a[n_] := Floor[66n/32] - Which[n == 6 || Mod[n, 8] == 5 || MemberQ[{2, 4, 7, 9, 11}, Mod[n, 16]] || MemberQ[{10, 15, 16, 24}, Mod[n, 32]], 1, MemberQ[{1, 3, 17, 19}, Mod[n, 32]], 2, True, 0];

Array[a, 100] (* Jean-François Alcover, Mar 28 2019, from Maple *)

PROG

(PARI) concat(0, Vec(-x^2*(x^35 -x^34 -x^33 +x^32 +x^31 -x^30 -x^29 -2*x^28 -x^27 -x^26 -2*x^24 -x^23 -x^22 -x^21 -x^20 -2*x^18 -2*x^17 -x^16 +x^15 -2*x^14 -2*x^13 -x^12 +x^11 -2*x^10 -2*x^9 -x^8 -x^6 -x^5 -2*x^4 -x^3 -x -3) / ((x -1)^2*(x +1)*(x^4 +1)*(x^8 +1)*(x^16 +1)) + O(x^10001))) \\ Colin Barker, Sep 22 2014

CROSSREFS

Cf. A245230, A245231, A245227, A245314.

Sequence in context: A272909 A035267 A309133 * A191978 A187477 A111499

Adjacent sequences:  A245236 A245237 A245238 * A245240 A245241 A245242

KEYWORD

nonn

AUTHOR

Robert Israel, Jul 14 2014

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 January 28 22:40 EST 2020. Contains 331328 sequences. (Running on oeis4.)