Bipartite subgraphs of integer weighted graphs (Q1381843)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bipartite subgraphs of integer weighted graphs |
scientific article |
Statements
Bipartite subgraphs of integer weighted graphs (English)
0 references
1 April 1998
0 references
For an integer-weighted graph \(G\), let \(f(G)\) denote the maximum total weight in a bipartite subgraph of \(G\). For every \(p>0\), let \(f(p)\) denote the minimum value of \(f(G)\), as \(G\) ranges over all integer-weighted graphs with total weight \(p\). The authors show that for every large \(n\) and every \(m<n\), one has \(f({n \choose 2} +m)= \lfloor {n^2 \over 4} \rfloor+ \min (\lceil {n\over 2} \rceil, f(m))\). This supplies the precise value of \(f(p)\) for many values of \(p\) including all \(p= {n \choose 2} +{m \choose 2}\) when \(n\) is large enough and \({m^2 \over 4} \leq{n \over 2}\).
0 references
integer-weighted graph
0 references
bipartite subgraph
0 references