Decomposition of complete graphs into small generalized prisms

Sylwia Cichacz, Dalibor Froncek, Mariusz Meszka

Research output: Contribution to journalArticlepeer-review


A prism is the Cartesian product Cm{square subset}P2. In other words, it is a graph consisting of two cycles of the same length whose corresponding vertices are joined by additional edges forming a matching. The problem of decomposition of complete graphs into prisms with 12 or 16 vertices was completely solved in [12]. In this paper we completely characterize the complete graphs that are decomposable into 3-regular bipartite graphs of order 12 or 16 that are a simple modification of prisms.

Original languageEnglish (US)
Pages (from-to)285-293
Number of pages9
JournalAKCE International Journal of Graphs and Combinatorics
Issue number3
StatePublished - Oct 1 2013


  • 3-regular bipartite graph
  • Graceful labeling
  • Graph decomposition
  • Prism
  • α-labeling


Dive into the research topics of 'Decomposition of complete graphs into small generalized prisms'. Together they form a unique fingerprint.

Cite this