To be or not to be Yutsis: Algorithms for the decision problem

Generalized recoupling coe! cients or 3nj-coe! cients can be expressed as multiple sums over products of Racah or 6j-coe! cients [1]. The problem of finding an optimal summation formula (i.e. with a minimal number of Racah coe! cients) for a given 3nj-coe! cient is equivalent to finding an optimal reduction of a so-called Yutsis graph [2]. In terms of graph theory Yutsis graphs are connected simple cubic graphs which can be partitioned into two vertex induced trees. The two parts are necessarily of the same size. In this area Yutsis graphs are also studied under the name of cubic dual Hamiltonian graphs [3]. We present algorithms for determining whether a cubic graph is a Yutsis graph. This is interesting for generating large test cases for programs (as in [4], [5] or [6]) that determine a summation formula for a 3njcoe! cient. Moreover, we give the numbers of Yutsis and non-Yutsis cubic graphs with up to 30 vertices and cubic polyhedra with up to 38 vertices. All these numbers have been computed by two independent programs in order to reduce the probability of error. Since the decision problem whether a given cubic graph is Yutsis or not is NP-complete, we couldn’t hope for a polynomial time worst case performance of our programs. Nevertheless the programs described in this article are very fast on average.