Quantcast

Decomposing the complete graph and the complete graph minus a 1-factor into copies of a graph G where G is the union of two disjoint cycles☆

Research paper by Saad I.El-Zanatia, UthoompornJongthawonwuthb, HeatherJordona, CharlesVanden Eyndena

Indexed on: 30 Oct '17Published on: 01 Aug '17Published in: European Journal of Combinatorics



Abstract

Let G<math class="math"><mi is="true">G</mi></math> of order n<math class="math"><mi is="true">n</mi></math> be the vertex-disjoint union of two cycles. It is known that there exists a G<math class="math"><mi is="true">G</mi></math>-decomposition of Kv<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">v</mi></mrow></msub></math> for all v≡1(mod2n)<math class="math"><mi is="true">v</mi><mo is="true">≡</mo><mn is="true">1</mn><mspace width="3.34pt" is="true"></mspace><mrow is="true"><mo is="true">(</mo><mo class="qopname" is="true">mod</mo><mspace width="3.34pt" is="true"></mspace><mn is="true">2</mn><mi is="true">n</mi><mo is="true">)</mo></mrow></math>. If G<math class="math"><mi is="true">G</mi></math> is bipartite and x<math class="math"><mi is="true">x</mi></math> is a positive integer, it is also known that there exists a G<math class="math"><mi is="true">G</mi></math>-decomposition of Knx−I<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">n</mi><mi is="true">x</mi></mrow></msub><mo is="true">−</mo><mi is="true">I</mi></math>, where I<math class="math"><mi is="true">I</mi></math> is a 1-factor. If G<math class="math"><mi is="true">G</mi></math> is not bipartite, there exists a G<math class="math"><mi is="true">G</mi></math>-decomposition of Kn<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub></math> if n<math class="math"><mi is="true">n</mi></math> is odd, and of Kn−I<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">−</mo><mi is="true">I</mi></math>, where I<math class="math"><mi is="true">I</mi></math> is a 1-factor, if n<math class="math"><mi is="true">n</mi></math> is even. We use novel extensions of the Bose construction for Steiner triple systems and some recent results on the Oberwolfach Problem to obtain a G<math class="math"><mi is="true">G</mi></math>-decomposition of Kv<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">v</mi></mrow></msub></math> for all v≡n(mod2n)<math class="math"><mi is="true">v</mi><mo is="true">≡</mo><mi is="true">n</mi><mspace width="3.34pt" is="true"></mspace><mrow is="true"><mo is="true">(</mo><mo class="qopname" is="true">mod</mo><mspace width="3.34pt" is="true"></mspace><mn is="true">2</mn><mi is="true">n</mi><mo is="true">)</mo></mrow></math> when n<math class="math"><mi is="true">n</mi></math> is odd, unless G=C4∪C5<math class="math"><mi is="true">G</mi><mo is="true">=</mo><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mn is="true">4</mn></mrow></msub><mo is="true">∪</mo><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mn is="true">5</mn></mrow></msub></math> and v=9<math class="math"><mi is="true">v</mi><mo is="true">=</mo><mn is="true">9</mn></math>. If G<math class="math"><mi is="true">G</mi></math> consists of two odd cycles and n≡0(mod4)<math class="math"><mi is="true">n</mi><mo is="true">≡</mo><mn is="true">0</mn><mspace width="3.34pt" is="true"></mspace><mrow is="true"><mo is="true">(</mo><mo class="qopname" is="true">mod</mo><mspace width="3.34pt" is="true"></mspace><mn is="true">4</mn><mo is="true">)</mo></mrow></math>, we also obtain a G<math class="math"><mi is="true">G</mi></math>-decomposition of Kv−I<math class="math"><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">v</mi></mrow></msub><mo is="true">−</mo><mi is="true">I</mi></math>, for all v≡0(modn)<math class="math"><mi is="true">v</mi><mo is="true">≡</mo><mn is="true">0</mn><mspace width="3.34pt" is="true"></mspace><mrow is="true"><mo is="true">(</mo><mo class="qopname" is="true">mod</mo><mspace width="3.34pt" is="true"></mspace><mi is="true">n</mi><mo is="true">)</mo></mrow></math>, v≠4n<math class="math"><mi is="true">v</mi><mo is="true">≠</mo><mn is="true">4</mn><mi is="true">n</mi></math>.