Decomposition of product graphs into complete bipartite subgraphs. (English) Zbl 0588.05034
Authors’ abstract: ”Let \(\tau\) (G) be the minimum number of complete bipartite subgraphs needed to partition the edges of G. Let \(G_{\bar n}\) be the weak product of cliques, \(K_{n_ 1}\times...\times K_{n_ i}\). This graph has vertices \(\{\) \(\bar x:\) \(0\leq x_ i<n_ i\}\), with edges between those vectors that differ in each coordinate. Theorem: \(\tau (G_{\bar n})=\sum_{| S| even}\prod_{i\not\in S}(n_ i-1).\)”
Reviewer: J.Schwarze
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C99 | Graph theory |
References:
| [1] | Graham, R. L.; Pollak, H. O., On embedding graphs in squashed cubes, Springer Lect. Notes in Math., 303, 99-110 (1973) · Zbl 0251.05123 |
| [2] | Lipshutz, S., Linear Algebra, ((1968), McGraw-Hill: McGraw-Hill New York), 265 |
| [3] | L. Lovász, unpublished.; L. Lovász, unpublished. |
| [4] | Peck, G. W., A new proof of a theorem of Graham and Pollak, Discrete Math., 49, 327-328 (1984) · Zbl 0533.05049 |
| [5] | Tverberg, H., On the decomposition of \(K_n\) into complete bipartite subgraphs, J. Graph Theory, 6, 493-494 (1982) · Zbl 0502.05048 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
