|
%I #18 Oct 28 2021 10:00:59
%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="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p10/pdf">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="http://epubs.siam.org/doi/abs/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
%O 1,6
%A _Robert Israel_, Jul 14 2014
|
