P. Botti, R. Merris and C. Vega, Laplacian permanents of trees, SIAM J. Discrete Math. 5 (1992), 460-466. Research supported by the National Security Agency under grant no. MDA904-90-H-4024. Math Reviews 95d:05085. Math Reviews 94d:15003.

The following fast algorithm computes the permanent of the Laplacian matrix of a tree:

Algorithm: Let T = (V,E) be a tree on two or more vertices.

Step 1. Initialize.

  • (a) Define p(v) = d(v), the degree of vertex v in V.
  • (b) Define q(e) = 1, for all e in E.

    • Step 2. Contract.

  • (a) Choose a pendant vertex x and let e = {x,y} be the (unique) edge of T incident with x.
  • (b) Replace p(y) with p(x)p(y) + q(e).
  • (c) For each edge e' incident with y, replace q(e') with p(x)q(e').
  • (d) Remove vertex x and edge e.

    • Step 3. Finished? If y is the only remaining vertex, go to Step 4. Otherwise, go to Step 2.

    Step 4. Answer: per(L(T)) = p(y).

    The algorithm leads to the following theorem [subsequently improved in publication 90].

    Theorem. Let tn be the number of (nonisomorphic, unlabeled) trees on n vertices. Let sn be the number of such trees T for which there exists a nonisomorphic tree T' such that per(L(T)) = per(L(T')). Then sn/tn is asymtotically equal to 1.

    Among the publications citing this article are:

  • K Balasubramanian, Chem. Phys. Letters 224 (1994), 325-332.