A245231 Maximum frustration of complete bipartite graph K(n,4).

0, 2, 3, 4, 5, 7, 8, 10, 10, 12, 13, 14, 15, 17, 18, 20, 20, 22, 23, 24, 25, 27, 28, 30, 30, 32, 33, 34, 35, 37, 38, 40, 40, 42, 43, 44, 45, 47, 48, 50, 50, 52, 53, 54, 55, 57, 58, 60, 60, 62, 63, 64, 65, 67, 68, 70, 70, 72, 73, 74, 75, 77, 78, 80, 80, 82, 83, 84, 85, 87, 88, 90, 90, 92, 93, 94, 95, 97, 98, 100

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(5*n/4) - 1 if n == 1, 4 or 5 mod 8,

a(n) = floor(5*n/4) otherwise.

G.f. x^2*(2*x^6+x^5+2*x^4+x^3+x^2+x+2)/(x^9-x^8-x+1).

a(n+8) = a(n) + 10.

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

Example

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

Maple

A:= n -> floor(5*n/4) - piecewise(member(n mod 8, {1, 4, 5}), 1, 0);
seq(A(n), n=1..100);

Mathematica

a[n_] := Floor[5n/4] - If[MemberQ[{1, 4, 5}, Mod[n, 8]], 1, 0];
Array[a, 100] (* Jean-François Alcover, Mar 28 2019, from Maple *)

Crossrefs

Cf. A245230, A245227, A245239, A245314.

Sequence in context: A111747 A257594 A101545 * A034154 A039262 A039202

Adjacent sequences: A245228 A245229 A245230 * A245232 A245233 A245234

Keyword

nonn

Author

Robert Israel, Jul 14 2014

Status

approved