|
|
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
|
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,3) = floor(3*m/4) = A057353(m).
|
|
LINKS
|
|
|
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
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|