On biclique partitions of the complete graph (Q686164)

From MaRDI portal
Revision as of 10:27, 30 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
On biclique partitions of the complete graph
scientific article

    Statements

    On biclique partitions of the complete graph (English)
    0 references
    0 references
    1 November 1993
    0 references
    Let \(X_ 1,\ldots,X_ m\) be a collection of 2-element subsets of the vertices of \(K_ n\). The author shows that there exist subsets \(Y_ 1,\ldots,Y_ m\) of vertices such that the edge-sets \(E_ i=\bigl\{ (a,b):a \in X_ i,\;b \in Y_ i \bigr\}\), \(i=1,\ldots,n\), form a partition of the edges of \(K_ n\) if and only if a certain graph has a complete matching. He also gives necessary and sufficient conditions for there to exist complete bipartite subgraphs \(K_{1,a_ 1}, \ldots,K_{s,a_ s}\) whose edge-sets form a partition of the edges of \(K_ n\), for given values of \(a_ 1,\ldots,a_ s\), when \(s=n-1\) or \(n\).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    biclique partitions
    0 references
    complete graph
    0 references
    complete matching
    0 references