A245227 Maximum frustration of complete bipartite graph K(n,5).

0, 2, 3, 5, 7, 9, 10, 12, 13, 15, 17, 18, 19, 21, 22, 25, 26, 27, 29, 30, 32, 34, 35, 37, 38, 40, 42, 43, 44, 46, 47, 50, 51, 52, 54, 55, 57, 59, 60, 62, 63, 65, 67, 68, 69, 71, 72, 75, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 94, 96, 97, 100, 101, 102

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(25/16*n) - 1 if n == 2,4,9,13, or 15 mod 16 or if n = 1 or 3; a(n) = floor(25/16*n) otherwise.

G.f.: -x^2*(x^18-x^17+x^16-x^15-3*x^14-x^13-2*x^12-x^11-x^10-2*x^9-2*x^8-x^7-2*x^6-x^5-2*x^4-2*x^3-2*x^2-x-2)/(x^17-x^16-x+1).

a(n+16) = a(n) + 25 for n > 3.

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

Example

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

Maple

A245227:= n -> floor(25/16*n) - piecewise(member(n mod 16, {2, 4, 9, 13, 15}), 1, 0):
A245227(1):= 0:
A245227(3):= 3:
seq(A245227(n), n=1..100);

Mathematica

a[n_] := Floor[25 n/16] - If[n == 1 || n == 3 || MemberQ[{2, 4, 9, 13, 15}, Mod[n, 16]], 1, 0];
Array[a, 100] (* Jean-François Alcover, Mar 27 2019, after Robert Israel *)

Crossrefs

Cf. A245230, A245231, A245239, A245314.

Sequence in context: A168543 A026277 A201804 * A226249 A076355 A081477

Adjacent sequences: A245224 A245225 A245226 * A245228 A245229 A245230

Keyword

nonn

Author

Robert Israel, Jul 14 2014

Status

approved