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

Ardeshir Dolati, Somayyeh Golalizadeh

Abstract


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 $13f_{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.

Keywords


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

Full Text: PDF