OFFSET
1,6
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.
T(m,n) is symmetric in m and n, so only m>=n is listed here.
T(m,1) = 0.
T(m,2) = floor(m/2) = A004526(m).
T(m,3) = floor(3*m/4) = A057353(m).
T(m,4) = A245231(m).
T(m,5) = A245227(m).
T(m,6) = A245239(m).
T(m,7) = A245314(m).
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
EXAMPLE
For m=n=3 a set of edges attaining the maximum cardinality T(3,3)=2 is {(1,4),(2,5)}.
Triangle starts
0;
0, 1;
0, 1, 2;
0, 2, 3, 4;
0, 2, 3, 5, 7;
0, 3, 4, 7, 9, 11;
0, 3, 5, 8, 10, 13, 16;
0, 4, 6, 10, 12, 16, 19, 22.
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Robert Israel, Jul 14 2014
STATUS
approved