Discussiones Mathematicae Graph Theory 32(4) (2012) 771-782
doi: 10.7151/dmgt.1646

[BIBTex] [PDF] [PS]

Sharp Bounds for the Number of Matchings in Generalized-theta-graphs

Ardeshir Dolati

Department of Mathematics & Computer Science
Shahed University, Tehran, PO Box: 18151-159, Iran

Somayyeh Golalizadeh

Young Researchers Club, Islamic Azad University
Ardabil branch, Ardabil, Iran


A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θnk. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θnk. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.

Keywords: generalized-theta-graph, matching, Fibonacci number, Hosoya index

2010 Mathematics Subject Classification: 05C30, 05C70, 05C75.


[1]H. Deng, The largest Hosoya index of (n, n + 1)-graphs, Comput. Math. Appl. 56 (2008) 2499--2506, doi: 10.1016/j.camwa.2008.05.020.
[2]H. Deng and S. Chen, The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem. 59 (2008) 171--190.
[3]A. Dolati, M. Haghighat, S. Golalizadeh and M. Safari, The smallest Hosoya index of connected tricyclic graphs, MATCH Commun. Math. Comput. Chem. 65 (2011) 57--70.
[4]T. Došlić and F. Måløy, Chain hexagonal cacti: Matchings and independent sets, Discrete Math. 310 (2010) 1676--1690, doi: 10.1016/j.disc.2009.11.026.
[5]I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer-Verlag, Berlin, 1986).
[6]H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971) 2332--2339, doi: 10.1246/bcsj.44.2332.
[7]H. Hua, Minimizing a class of unicyclic graphs by means of Hosoya index, Math. Comput. Modelling 48 (2008) 940--948, doi: 10.1016/j.mcm.2007.12.003.
[8]J. Ou, On extremal unicyclic molecular graphs with maximal Hosoya index, Discrete Appl. Math. 157 (2009) 391--397, doi: 10.1016/j.dam.2008.06.006.
[9]A. Syropoulos Mathematics of multisets, Multiset Processing, LNCS 2235, C.S. Calude, G. Păun, G. Rozenberg, A. Salomaa (Eds.), (Springer-Verlag, Berlin, 2001) 347--358, doi: 10.1007/3-540-45523-X_17.
[10]K. Xu, On the Hosoya index and the Merrifield-Simmons index of graphs with a given clique number, Appl. Math. Lett. 23 (2010) 395--398, doi: 10.1016/j.aml.2009.11.005.
[11]H. Zhao and X. Li, On the Fibonacci numbers of trees, Fibonacci Quart. 44 (2006) 32-?38.

Received 12 August 2011
Revised 25 January 2012
Accepted 30 January 2012