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

  • Ardeshir Dolati
  • Somayyeh Golalizadeh
Keywords: Matching, Fibonacci number, Hosoya index, tricyclic graph, connected graph


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.


Article Number