login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A245314
Maximum frustration of complete bipartite graph K(n,7).
5
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
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
KEYWORD
nonn,changed
AUTHOR
Robert Israel, Jul 17 2014
STATUS
approved