Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
decompositions; prism; $\rho ^+$-labeling
decompositions; prism; $\rho ^+$-labeling
Summary:
R. Frucht and J. Gallian (1988) 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 $\rho ^{+}$-labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) 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$.
References:
[1] Cichacz, S., Froncek, D.: Factorization of $K_{n,n}$ into $(0,j)$-prisms. Inf. Process. Lett. 109 (2009), 932-934. DOI 10.1016/j.ipl.2009.04.024 | MR 2541974 | Zbl 1197.05116
[2] Cichacz, S., Fronček, D., Kovář, P.: Note on decomposition of $K_{n,n}$ into $(0,j)$-prisms. Combinatorial Algorithms Lecture Notes in Computer Science 5874 Springer, Berlin (2009), 125-133. DOI 10.1007/978-3-642-10217-2_15 | MR 2577931 | Zbl 1267.05203
[3] Cichacz, S., Fronček, D., Kovář, P.: Decomposition of complete bipartite graphs into generalized prisms. Eur. J. Comb. 34 (2013), 104-110. DOI 10.1016/j.ejc.2012.07.018 | MR 2974274 | Zbl 1256.05184
[4] El-Zanati, S. I., Eynden, C. Vanden, Punnim, N.: On the cyclic decomposition of complete graphs into bipartite graphs. Australas. J. Comb. 24 (2001), 209-219. MR 1852820
[5] Frucht, R., Gallian, J.: Labeling prisms. Ars Comb. 26 (1988), 69-82. MR 0982109 | Zbl 0678.05053
[6] Huang, J. H., Skiena, S.: Gracefully labeling prisms. Ars Comb. 38 (1994), 225-242. MR 1310422 | Zbl 0818.05056
[7] Jungreis, D. S., Reid, M.: Labeling grids. Ars Comb. 34 (1992), 167-182. MR 1206560 | Zbl 0774.05087
[8] Rosa, A.: On certain valuations of the vertices of a graph. Theory of Graphs Int. Symp. Rome 1966 (1967), 349-355. MR 0223271 | Zbl 0193.53204
Search
Partner of
