Araştırma Makalesi
BibTex RIS Kaynak Göster
Yıl 2023, Cilt: 52 Sayı: 2, 356 - 366, 31.03.2023
https://doi.org/10.15672/hujms.1095437

Öz

Kaynakça

  • [1] R. B. Allan and R. Laskar On domination and independent domination numbers of a graph, Discrete Math. 23, 73-76, 1978.
  • [2] V. Andova, T. Došlić, M. Krnc, B. Lužar and R. Škrekovski, On the diameter and some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem. 68, 109-130, 2012.
  • [3] V. Andova, F. Kardoš and R. Škrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73, 501-518, 2015.
  • [4] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
  • [5] T. Biedl, E. D. Demaine, S. G. Kobourov, C. A. Duncan and R. Fleischer, Tight bounds on maximal and maximum matchings, Discrete Math. 285, 7-15, 2004.
  • [6] J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244. Springer, New York, 2008.
  • [7] G. Chartrand and L. Lesniak, Graphs & Digraphs, CRC Press, 2010.
  • [8] M. Demange and T. Ekim, Minimum maximal matching is NP-hard in regular bipartite graphs, Conference on Theory and Applications of Models of Computations, LNCS 4978, pp. 364–374, 2008.
  • [9] T. Došlić, Saturation number of fullerene graphs, J. Math. Chem. 43, 647-657, 2008.
  • [10] T. Došlić, Block allocation of a sequential resource, Ars Math. Contemp. 17, 79-88, 2019.
  • [11] T. Došlić and I. Zubac, Saturation Number of Benzenoid Graphs, MATCH Commun. Math. Comput. Chem. 73, 491-500, 2015.
  • [12] T. Došlić and I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11, 255-276, 2016.
  • [13] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory B 19, 87-95, 1975.
  • [14] W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313, 839-854, 2013.
  • [15] I. Gutman and S. J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons, Springer Verlag, Berlin, Heidelberg, 1989.
  • [16] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Taylor & Francis Group, 2011.
  • [17] J.D. Horton and K. Kilakos, Minimum edge dominating sets, SIAM J. Disc. Math. 6, 375-387, 1993.
  • [18] L. Lovász and M. D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.
  • [19] N. Tratnik and P. Žigert Pleteršek, Saturation Number of Nanotubes, Ars Math. Contemp. 12, 337-350, 2017.
  • [20] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996.
  • [21] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38, 364-372, 1980.
  • [22] M. Zito, Small maximal matchings in random graphs, Theoret. Comput. Sci. 297, 487-507, 2003.

Smallest maximal matchings of graphs

Yıl 2023, Cilt: 52 Sayı: 2, 356 - 366, 31.03.2023
https://doi.org/10.15672/hujms.1095437

Öz

Let $G=(V_G, E_G)$ be a simple and connected graph. A set $M\subseteq E_G$ is called a matching of $G$ if no two edges of $M$ are adjacent. The number of edges in $M$ is called its size. A matching $M$ is maximal if it cannot be extended to a larger matching in $G$. The smallest size of a maximal matching is called the saturation number of $G$. In this paper we are concerned with the saturation numbers of lexicographic product of graphs. We also address and solve an open problem about the size of maximum matchings in graphs with a given maximum degree $\Delta$.

Kaynakça

  • [1] R. B. Allan and R. Laskar On domination and independent domination numbers of a graph, Discrete Math. 23, 73-76, 1978.
  • [2] V. Andova, T. Došlić, M. Krnc, B. Lužar and R. Škrekovski, On the diameter and some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem. 68, 109-130, 2012.
  • [3] V. Andova, F. Kardoš and R. Škrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73, 501-518, 2015.
  • [4] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
  • [5] T. Biedl, E. D. Demaine, S. G. Kobourov, C. A. Duncan and R. Fleischer, Tight bounds on maximal and maximum matchings, Discrete Math. 285, 7-15, 2004.
  • [6] J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244. Springer, New York, 2008.
  • [7] G. Chartrand and L. Lesniak, Graphs & Digraphs, CRC Press, 2010.
  • [8] M. Demange and T. Ekim, Minimum maximal matching is NP-hard in regular bipartite graphs, Conference on Theory and Applications of Models of Computations, LNCS 4978, pp. 364–374, 2008.
  • [9] T. Došlić, Saturation number of fullerene graphs, J. Math. Chem. 43, 647-657, 2008.
  • [10] T. Došlić, Block allocation of a sequential resource, Ars Math. Contemp. 17, 79-88, 2019.
  • [11] T. Došlić and I. Zubac, Saturation Number of Benzenoid Graphs, MATCH Commun. Math. Comput. Chem. 73, 491-500, 2015.
  • [12] T. Došlić and I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11, 255-276, 2016.
  • [13] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory B 19, 87-95, 1975.
  • [14] W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313, 839-854, 2013.
  • [15] I. Gutman and S. J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons, Springer Verlag, Berlin, Heidelberg, 1989.
  • [16] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Taylor & Francis Group, 2011.
  • [17] J.D. Horton and K. Kilakos, Minimum edge dominating sets, SIAM J. Disc. Math. 6, 375-387, 1993.
  • [18] L. Lovász and M. D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.
  • [19] N. Tratnik and P. Žigert Pleteršek, Saturation Number of Nanotubes, Ars Math. Contemp. 12, 337-350, 2017.
  • [20] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996.
  • [21] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38, 364-372, 1980.
  • [22] M. Zito, Small maximal matchings in random graphs, Theoret. Comput. Sci. 297, 487-507, 2003.
Toplam 22 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Matematik
Bölüm Matematik
Yazarlar

Mostofa Tavakoli 0000-0002-3315-1759

‎tomislav Doslic Bu kişi benim 0000-0002-8326-513X

Yayımlanma Tarihi 31 Mart 2023
Yayımlandığı Sayı Yıl 2023 Cilt: 52 Sayı: 2

Kaynak Göster

APA Tavakoli, M., & Doslic, ‎. (2023). Smallest maximal matchings of graphs. Hacettepe Journal of Mathematics and Statistics, 52(2), 356-366. https://doi.org/10.15672/hujms.1095437
AMA Tavakoli M, Doslic ‎. Smallest maximal matchings of graphs. Hacettepe Journal of Mathematics and Statistics. Mart 2023;52(2):356-366. doi:10.15672/hujms.1095437
Chicago Tavakoli, Mostofa, ve ‎tomislav Doslic. “Smallest Maximal Matchings of Graphs”. Hacettepe Journal of Mathematics and Statistics 52, sy. 2 (Mart 2023): 356-66. https://doi.org/10.15672/hujms.1095437.
EndNote Tavakoli M, Doslic ‎ (01 Mart 2023) Smallest maximal matchings of graphs. Hacettepe Journal of Mathematics and Statistics 52 2 356–366.
IEEE M. Tavakoli ve ‎. Doslic, “Smallest maximal matchings of graphs”, Hacettepe Journal of Mathematics and Statistics, c. 52, sy. 2, ss. 356–366, 2023, doi: 10.15672/hujms.1095437.
ISNAD Tavakoli, Mostofa - Doslic, ‎tomislav. “Smallest Maximal Matchings of Graphs”. Hacettepe Journal of Mathematics and Statistics 52/2 (Mart 2023), 356-366. https://doi.org/10.15672/hujms.1095437.
JAMA Tavakoli M, Doslic ‎. Smallest maximal matchings of graphs. Hacettepe Journal of Mathematics and Statistics. 2023;52:356–366.
MLA Tavakoli, Mostofa ve ‎tomislav Doslic. “Smallest Maximal Matchings of Graphs”. Hacettepe Journal of Mathematics and Statistics, c. 52, sy. 2, 2023, ss. 356-6, doi:10.15672/hujms.1095437.
Vancouver Tavakoli M, Doslic ‎. Smallest maximal matchings of graphs. Hacettepe Journal of Mathematics and Statistics. 2023;52(2):356-6.