login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Triangle T(m,n), 1<=n<=m, read by rows: maximum frustration of complete bipartite graph K(m,n).
4

%I #23 Jan 04 2025 13:47:27

%S 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,

%T 12,16,19,22

%N Triangle T(m,n), 1<=n<=m, read by rows: maximum frustration of complete bipartite graph K(m,n).

%C 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.

%C T(m,n) is symmetric in m and n, so only m>=n is listed here.

%C T(m,1) = 0.

%C T(m,2) = floor(m/2) = A004526(m).

%C T(m,3) = floor(3*m/4) = A057353(m).

%C T(m,4) = A245231(m).

%C T(m,5) = A245227(m).

%C T(m,6) = A245239(m).

%C T(m,7) = A245314(m).

%H G. S. Bowlin, <a href="https://doi.org/10.37236/2204">Maximum Frustration in Bipartite Signed Graphs</a>, Electr. J. Comb. 19(4) (2012) #P10.

%H R. L. Graham and N. J. A. Sloane, <a href="http://www.math.ucsd.edu/~ronspubs/85_01_covering_radius.pdf">On the Covering Radius of Codes</a>, IEEE Trans. Inform. Theory, IT-31(1985), 263-290.

%H P. Solé and T. Zaslavsky, <a href="https://doi.org/10.1137/S0895480189174374">A Coding Approach to Signed Graphs</a>, SIAM J. Discr. Math 7 (1994), 544-553.

%e For m=n=3 a set of edges attaining the maximum cardinality T(3,3)=2 is {(1,4),(2,5)}.

%e Triangle starts

%e 0;

%e 0, 1;

%e 0, 1, 2;

%e 0, 2, 3, 4;

%e 0, 2, 3, 5, 7;

%e 0, 3, 4, 7, 9, 11;

%e 0, 3, 5, 8, 10, 13, 16;

%e 0, 4, 6, 10, 12, 16, 19, 22.

%Y Cf. A245231 (row/column 4), A245227 (row/column 5), A245239 (row/column 6), A245314 (row/column 7)

%K nonn,tabl,more

%O 1,6

%A _Robert Israel_, Jul 14 2014