Hosoya Index of a Graph

Description of the problem

A $k$-matching is a collection of edges of size $k$ in a graph in which any pair of edges share no vertices. Given a graph $G$ and an edge $vw$ in $G$, $m_k(G)$ the number of $k$-matchings in $G$ satisfies the following recurrence relation: \[ m_k(G) = 1 + m_{k-1}(G-v-w) + m_k(G-vw) \] where

$G-v-w$ is the graph obtained from $G$ by removing the vertices $v$ and $w$, and every edge incident to $u$ or $v$, and
$G-vw$ is the graph obtained from $G$ by removing the edge $vw$.

The counting formula relies on the fact that there are two classes of matchings: those that include $vw$, and those that do not. The size of the first class is $1+m_{k-1}(G-v-w)$ because if $vw$ is in a matching then those edges incident to $v$ or $w$ are not in that class. The size of the second class is $m_k(G-vw)$.

Now, the Hosoya Index of a graph is the sum $\sum_{k=0}^{|V|/2} m_k(G)$.

An implementation

I’ll use a list of edges to represent a graph. This time around, I am not going to include trivial edges.

(defparameter G '((0 1) (1 2) (2 3) (3 4) (0 3)))

Let me start with a utility function that removes a collection of vertices from a graph:

(defun delete-vertices (G vs)
  (if (or (null vs) (null G))
      G
      (delete-vertices (remove-if (lambda (edge) (member (car vs) edge)) G)
                       (cdr vs))))

(delete-vertices G '(4))

DELETE-VERTICES
((0 1) (1 2) (2 3) (0 3))

Now, my implementation of the Hosoya index:

(defun hosoya-index (H)
   (labels
      ((helper (H)
           (if (null H)
               0
               (+ 1
                  (helper (cdr H))
                  (helper (delete-vertices H (car H)))))))
     (1+ (helper H))))

(hosoya-index G)

HOSOYA-INDEX
10

Now, as before, I’ll re-define functions that return a standard list of graphs:

(defun line (n)
   (loop for i from 0 below (1- n) collect (list i (1+ i))))

(defun cycle (n)
   (append (line n) (list (list 0 (1- n)))))

(defun star (n)
   (loop for i from 0 below (1- n) collect (list i (1- n))))

(defun wheel (n)
   (union (cycle (1- n)) (star n)))

(defun complete (n)
   (loop for i from 0 below (1- n)
      append  (loop for j from (1+ i) below n
                 collect (list i j))))
            
(line 5)
(cycle 5)
(star 5)
(wheel 5)
(complete 5)

LINE
CYCLE
STAR
WHEEL
COMPLETE
((0 1) (1 2) (2 3) (3 4))
((0 1) (1 2) (2 3) (3 4) (0 4))
((0 4) (1 4) (2 4) (3 4))
((0 3) (2 3) (1 2) (0 1) (0 4) (1 4) (2 4) (3 4))
((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

Now, let us test the Hosoya index:

(loop for i from 2 to 16 collect (hosoya-index (line i)))
(loop for i from 3 to 16 collect (hosoya-index (cycle i)))
(loop for i from 4 to 16 collect (hosoya-index (wheel i)))
(loop for i from 3 to 16 collect (hosoya-index (complete i)))

(2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)
(4 7 11 18 29 47 76 123 199 322 521 843 1364 2207)
(10 19 36 66 120 215 382 673 1178 2050 3550 6121 10514)
(4 10 26 76 232 764 2620 9496 35696 140152 568504 2390480 10349536 46206736)

The first sequence is the Fibonacci sequence A000045, the second is the sequence of Lucas numbers A000032, the third is A061705, and finally the fourth and the last is A000085.