State-of-the-Art in Complete Graph Decomposition

Authors

  • Haslinda Ibrahim , Sharmila Karim

Abstract

Complete graph decomposition is one of the established areas of interest in combinatorics, and its uses have ignited
numerous studies. This paper will present a compendium of the beautiful algorithm of the complete graph
decomposition and focus on the decomposition into one-factorization, triangles and distinct circuits. The discussion
further is extended by employing the distinct circuit algorithm in listing n! permutation. The method to display
permutation is motivated through the process of wings movement in butterfly to develop distinct circuits from
complete graphs. The beauty of this method is using the concept of mirror image of the wings movement, and this
method is called Half Butterfly Method (HBM). In this development, a starter set will be constructed as a basis to
generate all distinct circuits. Several cases will be enumerated to further exemplify the algorithms

Published

2020-03-31

Issue

Section

Articles