The Tight Upper Bound for the Number of Matchings of Tricyclic Graphs

Ardeshir Dolati, Somayyeh Golalizadeh


In this paper, we determine the tight upper bound for the number of matchings of connected $n$-vertex tricyclic graphs. We show that this bound is $13 f_{n-4} + 16f_{n-5}$, where $f_n$ be the  $n$th Fibonacci number. We also  characterize the $n$-vertex simple connected tricyclic graph for which the bound is best  possible.

A corrigendum was added to this paper on Jun 17, 2015.



Matching; Fibonacci number; Hosoya index; tricyclic graph; connected graph

Full Text: PDF