|
|
A245314
|
|
Maximum frustration of complete bipartite graph K(n,7).
|
|
5
|
|
|
0, 3, 5, 8, 10, 13, 16, 19, 20, 22, 25, 28, 30, 32, 35, 38, 39, 42, 44, 47, 49, 52, 54, 57, 59, 60, 64, 66, 68, 71, 73, 76, 78, 81, 83, 85, 88, 91, 93, 95, 97, 100, 103, 105, 107, 110, 112, 115, 116, 119, 122, 124, 126, 129, 131, 134, 136, 139, 141, 143, 145
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = floor(154/64*n) - 1 if n = 2, 14, 17, 18, 36 or 49.
a(n) = floor(154/64*n) - 2 if n = 1, 3, 5, 10 or 26.
Otherwise a(n) = floor(154/64*n) if n == 7,12,14,16,17,22,24,26, or 27 mod 32
or 3,8,18,34,36,38,43,51, or 63 mod 64
Otherwise a(n) = floor(154/64*n) - 1.
a(n+64) = a(n) + 154 except for n = 1,2,3,5,10,14,17,18,26,36,49.
|
|
EXAMPLE
|
For n=2 a set of edges that achieves the maximum cardinality a(2) = 3 is {(1,3),(1,4),(1,5)}.
|
|
MAPLE
|
A245314:= n -> floor(154/64*n) - piecewise(
member(n, {2, 14, 17, 18, 36, 49}), 1,
member(n, {1, 3, 5, 10, 26}), 2,
member(n mod 32, {7, 12, 14, 16, 17, 22, 24, 26, 27}), 0,
member(n mod 64, {3, 8, 18, 34, 36, 38, 43, 51, 63}), 0,
1);
|
|
MATHEMATICA
|
a[n_] := Floor[154n/64] - Which[MemberQ[{2, 14, 17, 18, 36, 49}, n], 1, MemberQ[{1, 3, 5, 10, 26}, n], 2, MemberQ[{7, 12, 14, 16, 17, 22, 24, 26, 27}, Mod[n, 32]] || MemberQ[{3, 8, 18, 34, 36, 38, 43, 51, 63}, Mod[n, 64]], 0, True, 1];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|