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

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

Offset: 1

Author

Robert Israel, Jul 14 2014

Keywords

• nonn
• tabl
• more

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).

Examples

			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.
		

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.

Crossrefs

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