login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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).

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, IT-31(1985), 263-290

P. Solé and T. Zaslavsky, A Coding Approach to Signed Graphs, SIAM J. Discr. Math 7 (1994), 544-553

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 17:39 EDT 2021. Contains 348042 sequences. (Running on oeis4.)