

A245230


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


4



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

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.
The maximum frustration of a graph is the maximum cardinality of a set of edges that contains at most half the edges of any cutset. 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

Table of n, a(n) for n=1..36.
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, IT31(1985), 263290
P. SolĂ© and T. Zaslavsky, A Coding Approach to Signed Graphs, SIAM J. Discr. Math 7 (1994), 544553


EXAMPLE

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


CROSSREFS

Cf. A245231 (row/column 4), A245227 (row/column 5), A245239 (row/column 6), A245314 (row/column 7)
Sequence in context: A261097 A335335 A261217 * A284268 A063180 A263624
Adjacent sequences: A245227 A245228 A245229 * A245231 A245232 A245233


KEYWORD

nonn,tabl


AUTHOR

Robert Israel, Jul 14 2014


STATUS

approved



