A245314 Maximum frustration of complete bipartite graph K(n,7).

0, 3, 5, 8, 10, 13, 16, 19, 20, 22, 25, 28, 30, 32, 35, 38, 39, 42, 44, 47, 49, 52, 54, 57, 59, 60, 64, 66, 68, 71, 73, 76, 78, 81, 83, 85, 88, 91, 93, 95, 97, 100, 103, 105, 107, 110, 112, 115, 116, 119, 122, 124, 126, 129, 131, 134, 136, 139, 141, 143, 145

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(154/64*n) - 1 if n = 2, 14, 17, 18, 36 or 49.

a(n) = floor(154/64*n) - 2 if n = 1, 3, 5, 10 or 26.

Otherwise a(n) = floor(154/64*n) if n == 7,12,14,16,17,22,24,26, or 27 mod 32

or 3,8,18,34,36,38,43,51, or 63 mod 64

Otherwise a(n) = floor(154/64*n) - 1.

a(n+64) = a(n) + 154 except for n = 1,2,3,5,10,14,17,18,26,36,49.

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

Example

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

Maple

A245314:= n -> floor(154/64*n) - piecewise(
          member(n, {2, 14, 17, 18, 36, 49}), 1,
          member(n, {1, 3, 5, 10, 26}), 2,
          member(n mod 32, {7, 12, 14, 16, 17, 22, 24, 26, 27}), 0,
          member(n mod 64, {3, 8, 18, 34, 36, 38, 43, 51, 63}), 0,
          1);
seq(A245314(n), n=1..30);

Mathematica

a[n_] := Floor[154n/64] - Which[MemberQ[{2, 14, 17, 18, 36, 49}, n], 1, MemberQ[{1, 3, 5, 10, 26}, n], 2, MemberQ[{7, 12, 14, 16, 17, 22, 24, 26, 27}, Mod[n, 32]] || MemberQ[{3, 8, 18, 34, 36, 38, 43, 51, 63}, Mod[n, 64]], 0, True, 1];
Array[a, 100] (* Jean-François Alcover, Mar 28 2019, from Maple *)

Crossrefs

Cf. A245230, A245231, A245227, A245239.

Sequence in context: A077472 A184733 A004937 * A186150 A377206 A060606

Adjacent sequences: A245311 A245312 A245313 * A245315 A245316 A245317

Keyword

nonn

Author

Robert Israel, Jul 17 2014

Status

approved