A245239 Maximum frustration of complete bipartite graph K(n,6).

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

Offset: 1

Author

Robert Israel, Jul 14 2014

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Cf. A245230, A245231, A245227, A245314.

Programs

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

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

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