# On a Conjecture about the Saturation Number of Corona Product of Graphs

Authors: Mostafa Tavakoli
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG=VG,EG be a simple and connected graph. A set M⊆EG is called a matching if no two edges of M have a common endpoint. 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 confirm a conjecture of Alikhani and Soltani about the saturation number of corona product of graphs. We also present the exact value of sG∘H where H is a randomly matchable graph.


---

## Body

## 1. Introduction

All graphs considered in this paper are connected and simple; that is, they do not have loops and multiple edges [1–3]. For notation and graph theory terminology, we ingeneral follow [11, 12, 15].LetG=VG,EG be a graph. A collection of edges MG⊆EG is called a matching of G if no two edges of MG are adjacent. The vertices incident to the edges of a matching MG are said to be saturated by MG (or MG-saturated); the others are said to be unsaturated (or MG-unsaturated). A matching whose edges meet all vertices of G is called a perfect matching of G. If there does not exist a matching MG′in G such that MG<MG′, then MG is called a maximum matching of G. A matching MG is maximal if it cannot be extended to a larger matching in G. The cardinality of any maximum matching, νG, and the cardinality of any smallest maximal matching in G, sG, are called the matching number and the saturation number of G, respectively.If any maximal matching inG is also perfect (i.e., if sG=VG/2), then G is called randomly matchable.Smallest maximal matchings have a wide range of applications in real-world problems. For example, application of smallest maximal matchings related to a telephone switching network was presented in [4]. Finding a smallest maximal matching is NP-hard even for especial family of graphs (such as planar graphs), see [4–6]. Also, one can find some bounds for this invariant in [7–10]. See [10, 12,13] for more details on this topic. See [11–13] Recently, Alikhani and Soltani presented the following conjecture about the saturation number of corona product of graphs.Conjecture. [14] Let G and H be two graphs and VG=n. Then,(1)nsH≤sG∘H≤nsH+νG+l,where νG is the size of a maximum matching MG of the graph G and l is the number of M-unsaturated vertices of G.In this paper, we confirm this conjecture. We also present some more efficient results on the saturation number of corona product of graphs.For two graphs,G=VG,EG and H=VH,EH. The corona product of G and H, denoted by G∘H, is obtained from one copy of G and VG copies of H by joining each vertex of the ith copy of H, i∈1,…,VG, to the ith vertex of G, cf. [15]. In the following, for g∈VG, Hg shows the copy of H in G∘H corresponding to g.


## 2. Main Results

The first result of this section is the proof of the conjecture mentioned in the previous section.Theorem 1.
LetG and H be two graphs and |VG|=n. Then,(2)nsH≤sG∘H≤nsH+νG+l,where νG is the size of a maximum matching MG of the graph G and l is the number of M-unsaturated vertices of G.Proof.
First, we prove the upper bound. LetMG be a maximum matching of G, and MH be a maximal matching in H that MH=sH. Also, suppose that vertices g1,…,gl are M-unsaturated vertices of G. There are two cases for H.Case 1.H is a randomly matchable. Suppose that MG′ is a maximal matching in G that MG=sG. Set(3)M=MG′∪∪i=1nMHi,whereMHi is the ith copy of MH, i∈1,…,n, in Hi. Clearly, M is a maximal matching in G∘H. Thus,(4)sG∘H≤M=MG′∪∪i=1nMHi=sG+nsH<nsH+νG+l.Case 2.H is not a randomly matchable. Thus, MH is not a perfect matching. Suppose that hj is a MH-unsaturated of H. Set(5)M=MG∪∪i=1nMHi∪∪i=1lhjigi,wherehji is the copy of hj in Hi corresponding to gi. Easily one can check that M is a maximal matching in G∘H. Therefore,(6)sG∘H≤M=MG∪∪i=1nMHi∪∪i=1lhigji=nsH+νG+l.Now, we prove the lower bound. LetM be a maximal matching of G∘H. We consider two below cases for M.Case 1.M does not have any edges e so that e has one end in G and one end in a copy of H. Hence, M∩EHi≥sH, and consequently, nsH≤sG∘H.Case 2. Suppose g1hj11,g2hj22,…,gkhjkk be all edges of M such that gi∈VG and hjti∈VHi. Then, for each i∉1,…,k, we have M∩EHi=sH. Also, for each i∈1,…,k, we have sH−1≤M∩EHi≤sH. On the other hand,(7)g1h1,g2h2,…,gkhk∪∪i=1nM∩EHi⊆M.
Therefore,nsH≤sG∘H.
The next theorem gives the exact value ofsG∘H for some family of graphs.Theorem 2.
LetG be a graph of order n. If H is a randomly matchable graph, then(8)sG∘H=nsH.Proof.
By Theorem1, we have sG∘H≥nsH. Then, it is sufficient to prove that sG∘H≤nsH. Suppose hji is the copy of hj in Hi corresponding to gi. Let MH is a maximal matching of H, and MHi is the ith copy of MH, i∈1,…,n, in Hi. Assume that VG=g1,…,gn and hlht∈MH. Set(9)M=g1ht1,g2ht2,…,gnhtn∪∪i=1nMHi−hlihti.(For more illustration, see Figure 1 which is C3°C4. Suppose C4:=h1,h2,h3,h4,h1. Consider the maximal matching MC4=h1h2,h3h4. Since C4 is a randomly matchable graph, then M=g1h11,g2h12,g3h13∪h31h41,h32h42,h33h43,h34h44). According to this fact that H is a randomly matchable graph, then M is a maximal matching in G∘H. Thus,(10)sG∘H≤M=g1ht1,g2ht2,…,gnhtn∪∪i=1nMHi−hlihti.On the other hand, g1ht1,g2ht2,…,gnhtn∪∪i=1nMHi−hlihti=nsH−1+n=nsH. Therefore, sG∘H≤nsH.Figure 1
C3°C4.



---

*Source: 3375246-2022-09-28.xml*