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
KEYWORD
nonn
AUTHOR
Robert Israel, Jul 14 2014
STATUS
approved