On biclique partitions of the complete graph (Q686164)

From MaRDI portal





scientific article; zbMATH DE number 428008
Language Label Description Also known as
default for all languages
No label defined
    English
    On biclique partitions of the complete graph
    scientific article; zbMATH DE number 428008

      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
      biclique partitions
      0 references
      complete graph
      0 references
      complete matching
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references