zbMATH — the first resource for mathematics

Decomposition of complete graphs into \((0,2)\)-prisms. (English) Zbl 1340.05185
Summary: R. W. Frucht and J. A. Gallian [Ars Comb. 26, 69–82 (1988; Zbl 0678.05053)] proved that bipartite prisms of order \(2n\) have an \(\alpha \)-labeling, thus they decompose the complete graph \(K_{6nx+1}\) for any positive integer \(x\). We use a technique called the \(\varrho ^{+}\)-labeling introduced by S. I. El-Zanati et al. [Australas. J. Comb. 24, 209–219 (2001; Zbl 0983.05063)] to show that also some other families of 3-regular bipartite graphs of order \(2n\) called generalized prisms decompose the complete graph \(K_{6nx+1}\) for any positive integer \(x\).
05C51 Graph designs and isomorphic decomposition
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05B30 Other designs, configurations
Full Text: DOI
[1] S. Cichacz, D. Froncek: Factorization of K n,n into (0, j)-prisms. Inf. Process. Lett. 109 (2009), 932–934. · Zbl 1197.05116 · doi:10.1016/j.ipl.2009.04.024
[2] S. Cichacz, D. Fronček, P. Kovář: Note on decomposition of K n,n into (0, j)-prisms. Combinatorial Algorithms. Lecture Notes in Computer Science 5874, Springer, Berlin, 2009, pp. 125–133.
[3] S. Cichacz, D. Fronček, P. Kovář: Decomposition of complete bipartite graphs into generalized prisms. Eur. J. Comb. 34 (2013), 104–110. · Zbl 1256.05184 · doi:10.1016/j.ejc.2012.07.018
[4] S. I. El-Zanati, C. Vanden Eynden, N. Punnim: On the cyclic decomposition of complete graphs into bipartite graphs. Australas. J. Comb. 24 (2001), 209–219. · Zbl 0983.05063
[5] R. Frucht, J. Gallian: Labeling prisms. Ars Comb. 26 (1988), 69–82. · Zbl 0678.05053
[6] J. H. Huang, S. Skiena: Gracefully labeling prisms. Ars Comb. 38 (1994), 225–242. · Zbl 0818.05056
[7] D. S. Jungreis, M. Reid: Labeling grids. Ars Comb. 34 (1992), 167–182. · Zbl 0774.05087
[8] A. Rosa: On certain valuations of the vertices of a graph. Theory of Graphs. Int. Symp. Rome 1966, 1967, pp. 349–355.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.