On biclique partitions of the complete graph (Q686164): Difference between revisions
From MaRDI portal
Latest revision as of 11:05, 22 May 2024
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
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
biclique partitions
0 references
complete graph
0 references
complete matching
0 references
0 references
0 references