On Subgraphs of the Complete Bipartite Graph

From MaRDI portal





Mit \(B(m,n)\) werde ein Graph bezeichnet mit Punkten \(x_1,...,x_m, y_1,...,y_n\) und gewissen Kanten \(x_iy_j\), mit \(\bar B(m,n)\) der Graph mit den gleichen Punkten und jenen Kanten \(x_iy_i\), die nicht in \(B(m,n)\) enthalten sind. Enthält \(B(m,n)\) alle \(mn\) Kanten \(x_iy_j\), so wird er als vollständiger \((m,n)\)-Graph bezeichnet. \(C_{k,l}[B(m,n)]\) sei die Zahl der in \(B(m,n)\) enthaltenen vollständigen \((k,l)\)-Graphen. Dann ist \[ \lim_{m,n \to \infty} \min {{C_{k,l}[B(m,n)] + C_{k,l}[\bar B(m,n)]} \over {\binom{m}{k} \binom{n}{l}}} = {2 \over 2^{kl}}, \] wobei das Minimum über alle Graphen \(B(m,n)\) genommen wird.




Cited in
(25)








This page was built for publication: On Subgraphs of the Complete Bipartite Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5734986)