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

Generalized recoupling coefficients or 3nj-coefficients can be expressed as multiple sums over products of Racah or 6j-coefficients [L.C. Biedenharn, J.D. Louck, Coupling of n angular momenta: recoupling theory, in: The Racah-Wigner Algebra in Quantum Theory, Encyclopedia of Mathematics and its Applications, vol. 9, Addison-Wesley, 1981, pp. 435-481]. The problem of finding an optimal summation formula (i.e. with a minimal number of Racah coefficients) for a given 3nj-coefficient is equivalent to finding an optimal reduction of a so-called Yutsis graph [A.P. Yutsis, I.B. Levinson, V.V. Vanagas, Mathematical Apparatus of the Theory of Angular Momentum, Israel Program for Scientific Translation, Jerusalem, 1962]. 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 [F. Jaeger, On vertex-induced forests in cubic graphs, in: Proc. 5th Southeastern Conference, Congr. Numer. (1974) 501-512]. 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 [P.M. Lima, Comput. Phys. Comm. 66 (1991) 89; S. Fritzsche, T. Inghoff, T. Bastug, M. Tomaselli, Comput. Phys. Comm. 139 (2001) 314; D. Van Dyck, V. Fack, GYutsis: heuristic based calculation of general recoupling coefficients, Comput. Phys. Comm. 154 (2003) 219-232]) that determine a summation formula for a 3nj-coefficient. Moreover, we give the numbers of Yutsis and non-Yutsis cubic graphs with up to 30 vertices and cubic polyhedra with up to 40 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 could not hope for a polynomial time worst case performance of our programs. Nevertheless the programs described in this article are very fast on average.