Smallest maximal matchings of graphs

Mostofa Tavakoli

Makale detayları

Smallest maximal matchings of graphs

Yazarlar:

Mostofa Tavakoli

Yayıncı:

Hacettepe University

Ana Başlıklar:

Mathematical Sciences

Dergi:

Hacettepe Journal of Mathematics and Statistics Vol.52 Issue 2, pp.356-366

Belge Tipi:

Makale

Yayın Tarihi:

3/2023

Belge Dili:

İngilizce

Document ID (Org No.):

2001286624

pISSN:

2651-477X

Anahtar kelimeler:

Özet:

 Let GV_G, E_G be a simple and connected graph. A set Msubseteq 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.

 Let GV_G, E_G be a simple and connected graph. A set Msubseteq 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.

 Let GV_G, E_G be a simple and connected graph. A set Msubseteq 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.

 Let GV_G, E_G be a simple and connected graph. A set Msubseteq 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.

Makale detayları

Smallest maximal matchings of graphs

Yazarlar:

Mostofa Tavakoli

Yayıncı:

Hacettepe University

Ana Başlıklar:

Mathematical Sciences

Dergi:

Hacettepe Journal of Mathematics and Statistics Vol.52 Issue 2, pp.356-366

Belge Tipi:

Makale

Yayın Tarihi:

3/2023

Belge Dili:

İngilizce

Document ID (Org No.):

2001286624

pISSN:

2651-477X

maximal matching

product graph

saturation number

independent domination number

Sayı

Makale detayları

Smallest maximal matchings of graphs

Yazarlar: Mostofa Tavakoli

Yayıncı: Hacettepe University

Ana Başlıklar: Mathematical Sciences

Dergi: Hacettepe Journal of Mathematics and Statistics Vol.52 Issue 2, pp.356-366

Belge Tipi: Makale

Yayın Tarihi: 3/2023

Belge Dili: İngilizce

Document ID (Org No.): 2001286624

pISSN: 2651-477X

maximal matching

product graph

saturation number

independent domination number

Sayı

Yazarlar:

Mostofa Tavakoli

Yayıncı:

Hacettepe University

Ana Başlıklar:

Mathematical Sciences

Dergi:

Hacettepe Journal of Mathematics and Statistics Vol.52 Issue 2, pp.356-366

Belge Tipi:

Makale

Yayın Tarihi:

3/2023

Belge Dili:

İngilizce

Document ID (Org No.):

2001286624

pISSN:

2651-477X