On the Saturation Number of Graphs

Document Type : Research Paper

Authors

1 Yazd University, iran

2 Yazd University, Iran

Abstract

Let $G=(V,E)$ be a simple connected graph. A matching $M$ in a graph $G$ is a collection of edges of $G$ such that no two edges from $M$ share a vertex. A matching $M$ is maximal if it cannot be extended to a larger matching in $G$. The cardinality of any smallest maximal matching in $G$ is the saturation number of $G$ and is denoted by $s(G)$.
In this paper we study the saturation number of the corona product of two specific graphs. We also consider some graphs with certain constructions that are of importance in chemistry and study their saturation number.

Keywords

Main Subjects

References

1. S. Alikhani, S. Jahari, M. Mehryar and R. Hasni, Counting the number of dominating sets of cactus chains, Optoelectron. Adv. Mater. − Rapid Comm. 8 (9−10) (2014) 955−960.
2. V. Andova, F. Kardoš and R. Škrekovski, Sandwiching saturation number of fullerene graphs, arXiv:1405.2197 (2014).
3. S. J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, Vol. 46 Lecture Notes in Chemistry, Springer Science, Heidelberg, 1988.
4. E. Deutsch and S. Klavžar, Computing the Hosoya polynomial of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 627−644.
5. T. Došlić, On lower bounds of number of perfect matchings in fullerene graphs, J. Math. Chem. 24 (1998) 359−364.
6. T. Došlić, Fullerene graphs with exponentially many perfect matchings, J. Math. Chem. 41 (2007) 183−192.
7. T. Došlić, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008) 647−657.
8. T. Došlić and I. Zubac, Saturation number of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 73 (2015) 491−500.
9. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449−467.
10. J. Faudree, R. J. Faudree, R. J. Gould and M. S. Jacobson, Saturation numbers for trees, Electron. J. Combin. 16 (2009).
11. A. Frendrup, B. Hartnell and P. D. Vestergaard, A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185−190.
12. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994.
13. F. Kardoš, D. Král, J. Miškuf and J. S. Sereni, Fullerene graphs have exponentially many perfect matchings, J. Math. Chem. 46 (2009) 443−447.
14. M. Klažar, Twelve countings with rooted plane trees, European J. Combin. 18 (1997) 195−210.
15. L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Math. Vol. 29, North-Holland, Amsterdam, 1986.
16. S. G. Wagner, On the number of matchings of a tree, European J. Combin. 28 (2007) 1322−1330.
17. D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
18. H. Zhang and F. Zhang, New lower bound on the number of perfect matchings in fullerene graphs, J. Math. Chem. 30 (2001) 343−347.
Iranian Journal of Mathematical Chemistry
Volume 9, Issue 4
December 2018
Pages 289-299

Files

Share

How to cite

Statistics