Sharp bounds for the number of matchings in generalized-theta-graphs

Ardeshir Dolati; Somayyeh Golalizadeh

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 771-782
  • ISSN: 2083-5892

Abstract

top
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 Θⁿₖ. 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 Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.

How to cite

top

Ardeshir Dolati, and Somayyeh Golalizadeh. "Sharp bounds for the number of matchings in generalized-theta-graphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 771-782. <http://eudml.org/doc/270999>.

@article{ArdeshirDolati2012,
abstract = {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 Θⁿₖ. 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 Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.},
author = {Ardeshir Dolati, Somayyeh Golalizadeh},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {generalized-theta-graph; matching; Fibonacci number; Hosoya index; tricyclic graph; connected graph},
language = {eng},
number = {4},
pages = {771-782},
title = {Sharp bounds for the number of matchings in generalized-theta-graphs},
url = {http://eudml.org/doc/270999},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Ardeshir Dolati
AU - Somayyeh Golalizadeh
TI - Sharp bounds for the number of matchings in generalized-theta-graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 771
EP - 782
AB - 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 Θⁿₖ. 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 Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.
LA - eng
KW - generalized-theta-graph; matching; Fibonacci number; Hosoya index; tricyclic graph; connected graph
UR - http://eudml.org/doc/270999
ER -

References

top
  1. [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. Zbl1165.05321
  2. [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. Zbl1141.05049
  3. [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. Zbl1265.05454
  4. [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. Zbl1222.05197
  5. [5] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer-Verlag, Berlin, 1986). Zbl0657.92024
  6. [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. [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. Zbl1156.05328
  8. [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. Zbl1200.05241
  9. [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₁7. 
  10. [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. Zbl1218.05073
  11. [11] H. Zhao and X. Li, On the Fibonacci numbers of trees, Fibonacci Quart. 44 (2006) 32-38. Zbl1133.11011

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.