A Note on Bounded Biclique Coverings of Complete Graphs
Gu, Brian
Original · EN
An undirected biclique Kₐ,b is a graph with vertices partitioned into two sets: a set A containing a vertices and a set B containing b vertices such that every vertex in set A is connected to every vertex in set B, and such that no two vertices in the same set have an edge between them. A well-known result is that a minimum of ₂n bicliques graphs of any size are needed to edge-cover the complete graph on n vertices. We prove a lower bound on minimum vertex-weighted biclique coverings of the complete graph n, and use this to prove an asymptotic formula for the minimum number of bicliques Kₓ,ₓ with bounded component size needed to cover the complete graph on n vertices.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.