Smallest maximal matchings of graphs

Mostofa Tavakoli

Article Details

Smallest maximal matchings of graphs

Authors:

Mostofa Tavakoli

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

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

Document Type:

Article

Publication Date:

3/2023

Document Language:

English

Document ID (Org No.):

2001286624

pISSN:

2651-477X

Keywords:

Abstract:

 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.

Article Details

Smallest maximal matchings of graphs

Authors:

Mostofa Tavakoli

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

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

Document Type:

Article

Publication Date:

3/2023

Document Language:

English

Document ID (Org No.):

2001286624

pISSN:

2651-477X

maximal matching

product graph

saturation number

independent domination number

Issues

Article Details

Smallest maximal matchings of graphs

Authors: Mostofa Tavakoli

Publisher: Hacettepe University

Main Topics: Mathematical Sciences

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

Document Type: Article

Publication Date: 3/2023

Document Language: English

Document ID (Org No.): 2001286624

pISSN: 2651-477X

maximal matching

product graph

saturation number

independent domination number

Issues

Authors:

Mostofa Tavakoli

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

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

Document Type:

Article

Publication Date:

3/2023

Document Language:

English

Document ID (Org No.):

2001286624

pISSN:

2651-477X