# Domination Numbers of Amalgamations of Cycles at Connected Subgraphs

Authors: Prakassawat Boonmee; Jirapa Ma - In; Sayan Panma
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A setS of vertices of a graph G is a dominating set of G if every vertex in VG is adjacent to some vertex in S. A minimum dominating set in a graph G is a dominating set of minimum cardinality. The cardinality of a minimum dominating set is called the domination number of G and is denoted by γG. Let G1 and G2 be disjoint graphs, H1 be a subgraph of G1, H2 be a subgraph of G2, and f be an isomorphism from H1 to H2. The amalgamation (the glued graph) of G1 and G2 at H1 and H2 with respect to f is the graph G=G1⊲⊳G2H1≅fH2 obtained by forming the disjoint union of G1 and G2 and then identifying H1 and H2 with respect to f. In this paper, we determine the domination numbers of the amalgamations of two cycles at connected subgraphs.


---

## Body

## 1. Introduction

Studying on several graph parameters is an interesting topic in graph theory. The domination number is one of the most importance parameter which was introduced from 1958 by Berge [1], called as “coefficient of external stability.” In 1962, Ore [2] studied the same concept and used the name “dominating set” and “domination number” for a graph. In 1977, Cockayane and Hedetneimi [3] gave a survey of the results about dominating sets and used the notation γG for the domination number of a graph. In 1998, a text devoted to this subject was introduced by Haynes et al. [4]. Over 2000 articles on graph domination numbers have been studied extensively (see, for example, [2, 3, 5–16]), in particular, the study of the domination number of product graphs such as the Cartesian product of two cycles [12], the cross product of two paths [8], and the lexicographic product of two graphs [16]. It is natural to investigate the domination number of the amalgamation of two graphs, especially, the domination number of the amalgamation of two paths or two cycles.LetG1 and G2 be disjoint graphs and H1⊆G1 and H2⊆G2 such that H1≅H2. Let f be an isomorphism from H1 to H2. The amalgamation (the glued graph) of G1 and G2 at H1 and H2 with respect to f is the graph G=G1⊲⊳G2H1≅fH2 obtained by forming the disjoint union of G1 and G2 and then identifying H1 and H2 with respect to f. Equivalently, G=G1⊲⊳G2H1≅fH2 is the graph such that(1)VG=VG1−VH1∪VG2−VH2∪v,fv|v∈VH1EG=EG1−VH1∪EG2−VH2∪u,v,fv|u,v∈EG1∪u,v,fv|u,fv∈EG2∪u,fu,v,fv|u,v∈EG1orfu,fv∈EG2.Note that ifu,v∈EG1 and fu,fv∈EG2, then u,v∈EH1 and fu,fv∈EH2. As an example, Figure 1 illustrates the amalgamation G1⊲⊳G2H1≅fH2 with respect to the isomorphism f:H1⟶H2 defined by fv1=u1,fv2=u2, and fv3=u4. The amalgamation or the glued graph of two graphs was defined from 2003 by Uiyyasathian [17] for solving the maximal-clique partition problem. In 2006, Promsakon and Uiyyasathian [18] gave an upper bound of the chromatic number of glued graphs in terms of the chromatic numbers of their original graphs. Here, we are interested in finding the domination number of an amalgamation of two cycles at connected subgraphs.Figure 1
An amalgamation ofG1 and G2 at H1 and H2 with respect to f.


## 2. Basic Definitions and Results

A graphH is a subgraph of a graph G if VH⊆VG and EH⊆EG. In this case, we write H⊆G, and we say that G contains H. When H⊆G but H≠G, we write H⊂G and call H a proper subgraph of G. For a vertex v of a graph G, a neighbor of v is a vertex adjacent to v in G. The neighborhood (or open neighborhood)Nv of v is the set of neighbors of v. The closed neighborhoodNv is defined as Nv=Nv∪v. A vertex v in a graph G is said to dominate itself and each of its neighbors, that is, v dominates the vertices in its closed neighborhood. Therefore, v dominates 1+degv vertices. For a set S of vertices of a graph G, the closed neighborhoodNS is defined as NS=∪v∈SNv. A set S of vertices of a graph G is said to dominate the vertices in NS. A set S of vertices of a graph G is a dominating set of G if every vertex of G is dominated by some vertex in S, i.e., every vertex in VG−S is adjacent to some vertex in S. A minimum dominating set in a graph G is a dominating set of minimum cardinality. The cardinality of a minimum dominating set is called the domination number of G, and is denoted by γG. A dominating set of a graph G with minimum cardinality is called a γ−set of G.Since the cardinality of the vertex set of a graphG is finite, the number of dominating sets of G with minimum cardinality is finite too. This gives, for a given graph G of order n, the domination number can have a value from the following range: 1≤γG≤n. In particular, γG=1 if and only if Δ=n−1, where Δ is the maximum degree of G. Let Pn denote a path of order n such that VPn=v1,v2,…,vn and EPn=vi,vi+1|i=1,2,…,n−1. Let Cn denote a cycle of order n (n≥3) such that VCn=v1,v2,…,vn and ECn=vi,vi+1|i=1,2,…,n, where + is the addition modulo n. It is easy to obtain that γCn=γPn=⌈n/3⌉, where ⌈x⌉ is the least integer greater than or equal to x.A graphG is isomorphic to a graph H if there is a bijection f:VG⟶VH such that u,v∈EG if and only if fu,fv∈EH. If such a function exists, it is called an isomorphism from G to H and written by G≅H. A graph automorphism is simply an isomorphism from a graph to itself. Let IsoG,H denote the set of all isomorphisms from a graph G to a graph H and AutG denote the set of all automorphisms on a graph G. It is easy to see that if H is a connected subgraph of Cn, then either H≅P1,P2,…,Pn−1,Pn or Cn. Moreover, AutPn,Pn=f1,f2 such that f1vi=vi and f2vi=vn−i+1 for all i=1,2,…,n. Let H1 be a connected proper subgraph of Cr and H2 a connected proper subgraph of Ct such that VCr=v1,v2,…,vr, ECr=vi,vi+1|i=1,2,…,r, VCt=u1,u2,…,ut, and ECt=ui,ui+1|i=1,2,…,t. It follows that if H1≅H2, then H1 and H2 are paths of order s for some s≤minr,t such that VH1=vi+1,vi+2,…,vi+s and VH2=uj+1,uj+2,…,uj+s, for some i∈1,2,…,r and j∈1,2,…,t. We thus get IsoH1,H2=f1,f2 such that f1vi+q=uj+q and f2vi+q=uj+s−q+1, for all q=1,2,…,s. Figures 2 and 3 illustrate Cr⊲⊳CtH1≅f1H2 and Cr⊲⊳CtH1≅f2H2, respectively.Figure 2
The amalgamation ofCr and Ct at connected proper subgraphs H1 and H2 with respect to f1.Figure 3
The amalgamation ofCr and Ct at connected proper subgraphs H1 and H2 with respect to f2.It is easily seen thatCr⊲⊳CtH1≅f1H2≅Cr⊲⊳CtH1≅f2H2. Moreover, if H1,H1′⊆Cr and H1≅H1′, then Cr⊲⊳CtH1≅fH2≅Cr⊲⊳CtH1′≅f′H2′ for all f∈IsoH1,H2 and f′∈IsoH1′,H2′. This implies the following lemma.Lemma 1.
LetH1⊆Cr, H1′⊆Cr, H2⊆Ct, and H2′⊆Ct be connected such that H1≅H1′≅H2≅H2′. Then γCr⊲⊳CtH1≅fH2=γCr⊲⊳CtH1′≅f′H2′ for all f∈IsoH1,H2 and f′∈IsoH1′,H2′.The next lemma gives the domination number ofCr⊲⊳CtH1≅fH2 for the case H1=Cr.Lemma 2.
IfH1=Cr, then r=t and γCr⊲⊳CtH1≅fH2=⌈r/3⌉.Proof.
LetH1=Cr and G=Cr⊲⊳CtH1≅fH2. Since H1≅H2, it follows easily that r=t and G≅Cr. We thus get γG=γCr=⌈r/3⌉.
We now turn to the caseH1≠Cr. So, H1≅H2≅Ps, for some s≤minr,t. Assume, without loss of generality, that minr,t=r, i.e., 3≤r≤t. For simplicity of notation, we write G instead of Cr⊲⊳CtH1≅fH2. Based on the result of Lemma 1, from now on, we can assume that VH1=v1,v2,…,vs and VH2=u1,u2,…,us, and the isomorphism f:H1⟶H2 is defined by fvi=ui, for all i=1,2,…,s. So, v1,u1,v2,u2,…,vs,us∈VG. Now, we consider γG with H1≅P1.Lemma 3.
IfH1≅P1, then γG=⌈r−3/3⌉+⌈t−3/3⌉+1.Proof.
Suppose thatH1≅P1. Then, v1,u1∈VG (see Figure 4(a)).
LetS=v1,u1∪vi|i≡1mod3,3≤i≤r−1∪ui|i≡1mod3,3≤i≤t−1. We check at once that S is a dominating set of G and S=⌈r−3/3⌉+⌈t−3/3⌉+1. This gives γG≤⌈r−3/3⌉+⌈t−3/3⌉+1. Let S′ be a γ− set of G. Thus, v1,u1∈S′ since otherwise S′ is not a γ− set of G. In order to dominate the vertices in G−Nv1,u1, then S−v1,u1 must contain at least ⌈r−3/3⌉+⌈t−3/3⌉ vertices. This gives γG=S′≥⌈r−3/3⌉+⌈t−3/3⌉+1. It follows that γG=⌈r−3/3⌉+⌈t−3/3⌉+1.
Now, we considerγG with H1≅Pr and define sets S and S′ as follows:S=vi,ui|i≡1mod3,1≤i≤r∪ui|i≡2mod3,r+1≤i≤t,S′=vi,ui|i≡1mod3,1≤i≤r∪ui|i≡1mod3,r+1≤i≤t.
Note thatS=⌈r/3⌉+⌈t−r−1/3⌉ and S′=⌈t/3⌉.Figure 4
Cr⊲⊳CtH1≅fH2 with H1≅P1, H1≅P2, and H1≅P3.
(a)(b)(c)Lemma 4.
LetH1≅Pr. Then,(2)γG=r/3+t−r−1/3ifr≡0mod3andt≡1mod3,t/3otherwise.Proof.
Suppose thatH1≅Pr. Then, v1,u1,…,vr,ur∈VG (see Figure 5(a)).
Ifr=t, then G is the graph obtained from Ct by joining v1 and vt with a new edge. It follows easily that γG=γCt=⌈t/3⌉. For r≠t, we consider two cases.Figure 5
Cr⊲⊳CtH1≅fH2 with H1≅Pr and H1≅Pr−1.
(a)(b)Case 1.r≡0mod3 and t≡1mod3. We check at once that the set S defined above is a dominating set of G. Thus, γG≤⌈r/3⌉+⌈t−r−1/3⌉. We now prove that γG≥⌈r/3⌉+⌈t−r−1/3⌉. Let S1 be a γ− set of G. In order to dominate v1,u1, S1 must contain at least one vertex of v1,u1,v2,u2,vr,ur,ut. There are two possible cases: either v1,u1∈S1 or vr,ur∈S1 since otherwise S1 is not a γ− set of G. We give the proof only for the case v1,u1∈S1; the proof of the case vr,ur∈S1 is similar. Consider the vertices of G−Nv1,u1≅Pr−3∪Pt−r−1. In order to dominate v3,u3,…,vr−1,ur−1 and ur+1,…,ut−1, there are at least ⌈r−3/3⌉+⌈t−r−1/3⌉ vertices of v2,u2,…,vr−1,ur−1∪ur+1,…,ut in S1−v1,u1. This gives |S1|≥1+⌈r−3/3⌉+⌈t−r−1/3⌉, so γG≥⌈r/3⌉+⌈t−r−1/3⌉. Hence, γG=⌈r/3⌉+⌈t−r−1/3⌉.Case 2.r≡0mod3 or t≡1mod3. We see at once that the set S′ defined above is a dominating set of G. Thus, γG≤⌈t/3⌉. We now prove that γG≥⌈t/3⌉. Let S2 be a γ− set of G. We consider two subcases.Case 2.1.r≡0mod3 and t≡0mod3 and r≡1mod3 and t≡amod3, for some a∈0,1,2, or r≡2mod3 and t≡amod3, for some a∈0,2.Case 2.1.1v1,u1∈S2 or vr,ur∈S2. If v1,u1∈S2 and t>r+1, then, in order to dominate v3,u3,…,vr−1,ur−1 and ur+2,…, ut−1, there are at least ⌈r−3/3⌉+⌈t−r−2/3⌉ vertices of v2,u2,…,vr,ur∪ur+1,…,ut in S2−v1,u1. It follows that S2≥1+⌈r−3/3⌉+⌈t−r−2/3⌉=⌈t/3⌉. If v1,u1∈S2 and t=r+1, then ur+2,…ut−1=∅. So, in order to dominate the vertices in G−Nv1,u1, there are at least ⌈r−3/3⌉ vertices of v2,u2,…,vr,ur in S2−v1,u1. This gives S2≥1+⌈r−3/3⌉=⌈t/3⌉. Similarly, if vr,ur∈S2, then S2≥⌈t/3⌉. Thus, γG≥⌈t/3⌉.Case 2.1.2.v1,u1∉S2 and vr,ur∉S2. Clearly, γG=S2≥γCt=⌈t/3⌉.Case 2.2.r≡0mod3 and t≡2mod3 or r≡2mod3 and t≡1mod3.Case 2.2.1. eitherv1,u1∈S2 or vr,ur∈S2. If v1,u1∈S2, then, in order to dominate v3,u3,…,vr,ur,ur+1,…, ut−1 in G, there are at least ⌈t−3/3⌉ vertices of v2,u2,…,vr,ur,ur+1,…,ut, in S2−v1,u1. It follows that S2≥1+⌈t−3/3⌉=⌈t/3⌉. Similarly, if vr,ur∈S2, then S2≥⌈t/3⌉. Thus, γG≥⌈t/3⌉.Case 2.2.2.v1,u1∈S2 and vr,ur∈S2. If r>3 and t>r+1, then, in order to dominate v3,u3,…,vr−2,ur−2 and ur+2,…,ut−1, there are at least ⌈r−4/3⌉ + ⌈t−r−2/3⌉ vertices of v2,u2,…,vr−1,ur−1∪ur+1,…,ut in S2. Hence, S2≥2+⌈r−4/3⌉+⌈t−r−2/3⌉=⌈t/3⌉. If r=3 and t>r+1, then there are at least ⌈t−r−2/3⌉ vertices of ur+1,…,ut in S2. The result is S2≥2+⌈t−r−2/3⌉=⌈t/3⌉. If r>3 and t=r+1, then there are at least ⌈r−4/3⌉ vertices of v2,u2,…,vr−1,ur−1. We thus get S2≥2+⌈r−4/3⌉=⌈t/3⌉. Clearly, if r=3 and t=r+1, then t=4 and S2≥2=⌈t/3⌉. Thus, γG≥⌈t/3⌉.Case 2.2.3.v1,u1∉S2 and vr,ur∉S2. Clearly, γG=S2≥γCt=⌈t/3⌉.Lemma 5.
IfH1≅P2, then(3)γG=r3+t−33ifr≡0mod3andt≡0mod3,t+r−23otherwise.Proof.
Suppose thatH1≅P2. It is easy to check that G=Cr⊲⊳CtH1≅fH2≅Cr⊲⊳Ct′H1′≅f′H2′ where H1′≅Pr and t′=t+r−2 (see Figures 4(b) and 5(a)). By Lemma 4, the result holds.
Next, we will give the domination number ofG such that H1≅P3 (r>3). We define three sets S0, S1, and S2 as follows:S0=v1,u1∪ui|i≡1mod3,4≤i≤t∪vi|i≡2mod3,4≤i≤r.S1=v1,u1∪ui|i≡2mod3,4≤i≤t∪vi|i≡1mod3,4≤i≤r.S2=v1,u1∪ui|i≡0mod3,4≤i≤t∪vi|i≡0mod3,4≤i≤r.
Note that ift≡jmod3, for some j∈0,1,2, then Sj=⌈r+t−7/3⌉+1.Lemma 6.
IfH1≅P3 and r>3, then γG=⌈r+t−7/3⌉+1.Proof.
Suppose thatH1≅P3. Then, v1,u1,v2,u2,v3,u3∈VG (see Figure 4(c)). Note that if t≡jmod3, for some j∈0,1,2, then the set Sj defined above is a dominating set of G, so γG≤⌈r+t−7/3⌉+1. We now prove that γG≥⌈r+t−7/3⌉+1. Let S be a γ− set of G. If r=4, then, in order to dominate vertices v1,u1,v2,u2,v3,u3,u4,…,ut, there are at least ⌈t/3⌉ vertices of v1,u1,v2,u2,v3,u3,u4,…,ut∪v4 in S. Thus, γG=S≥⌈t/3⌉=⌈4+t−7/3⌉+1. For r≥5, we consider two cases.Case 1.v1,u1∈S. In this case, we consider two subcases.Case 1.1.v3,u3∈S. Consider the vertices in G−Nv1,u1,v3,u3≅Pr−5∪Pt−5. We see that there are at least ⌈r−5/3⌉+⌈t−5/3⌉ vertices in S−v1,u1,v3,u3. This gives S≥⌈r−5/3⌉+⌈t−5/3⌉+2≥⌈r+t−7/3⌉+1.Case 1.2.v3,u3∉S. Consider the vertices in G−Nv1,u1≅Pr+t−7. We see at once that there are at least ⌈r+t−7/3⌉ vertices in S−v1,u1. It follows that S≥⌈r+t−7/3⌉+1.Case 2.v1,u1∉S. In order to dominate v1,u1, one vertex of v2,u2,vr,ut must be in S.Case 2.1.v2,u2∈S. Consider the vertices in G−Nv2,u2. In order to dominate v4,…,vr and u5,…,ut, there are at least ⌈r−3/3⌉+⌈t−4/3⌉ vertices in S−v2,u2. It follows that S≥⌈r−3/3⌉+⌈t−4/3⌉+1≥⌈r+t−7/3⌉+1.Case 2.2.vr∈S. If v2,u2∈S, then this case is the same as Case 2.1. If v2,u2∉S, then, in order to dominate ut,…,u4,v3,u3,v4,…,vr−2 in G−Nvr, S−vr contains at least ⌈t+r−7/3⌉ vertices. This gives S≥⌈r+t−7/3⌉+1.Case 2.3.ut∈S. By the same argument as in Case 2.2, we also get S≥⌈r+t−7/3⌉+1.Lemma 7.
IfH1≅Pr−1, then γG=⌈t−3/3⌉+1.Proof.
Suppose thatH1≅Pr−1. It is easy to check that G=Cr⊲⊳CtH1≅fH2≅Cr⊲⊳Ct′H1′≅f′H2′, where H1′≅P3 and t′=t−r+4 (see Figures 4(c) and 5(b)). By Lemma 6, the result holds.
By Lemma3–7, we know the domination number of G, for all r such that 3≤r≤5. We also know the domination number of G, for all H1 such that H1≅P1,P2,P3,Pr−1,Pr. We now consider the case r≥6 and H1≅P4,P5,…,Pr−2.
Forn,k,m∈ℕ−1,2, let us denote by Cm,k,n a graph with VCm,k,n=1,x∪2m,3m,…,mm∪2k,3k,…,kk∪2n,3n,…,nn and ECm,k,n=∪q∈m,k,n1,2q,2q,3q,…,q−1q,qq,qq,x. Figure 6 illustrates Cm,k,n.Figure 6
Cm,k,n.Lemma 8.
IfH1≅Ps, for some s∈4,5,…,r−2 and r≥6, then G≅Cm,k,n where r=m+k, s=k+1, and t=n+k.Proof.
Suppose thatH1≅Ps, for some s∈4,5,…,r−2 and r≥6. Let r=m+k, s=k+1, and t=n+k. Define f:VG⟶VCm,k,n by(4)fg=1ifg=v1,u1,ikifg=vi,uiand2≤i≤s−1,m−i+1mifg=vs+iand1≤i≤r−s,n−i+1nifg=us+iand1≤i≤t−s,xifg=vs,us.
It is easy to check thatf is an isomorphism. Then, G≅Cm,k,n.


## 3. Domination Numbers of Amalgamations of Cycles at Connected Subgraphs

In this section, we calculate the domination numberγCm,k,n. Then, by Lemma 8, we thus get the domination number γG for the case r≥6 and H1≅P4,P5,…,Pr−2. The following two lemmas provide upper bounds of γCm,k,n.Lemma 9.
Letm,k,n∈ℕ−1,2 and S=1,x∪∪q∈m,k,naq|a≡1mod3,3≤a≤q−1. Then, S is a dominating set of Cm,k,n and S=2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Proof.
Letv∈VCm,k,n−S. If v=2q, for some q∈m,k,n, then there is 1∈S such that 1,v∈ECm,k,n. If v=qq, for some q∈m,k,n, then there is x∈S such that x,v∈ECm,k,n. If v=uq, for some q∈m,k,n, such that u≡0mod3 and u∉m,k,n, then u+1≡1mod3 and thus u+1q∈S. It follows that there is u+1q∈S such that v,u+1q∈ECm,k,n. If v=uq, for some q∈m,k,n, such that u≡2mod3 and u∉2,m,k,n, then u−1≡1mod3 and thus u−1q∈S. Hence, there is u−1q∈S such that v,u−1q∈ECm,k,n. Therefore, S is a dominating set of Cm,k,n. It is easily seen that S=2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Lemma 10.
Letn,k,m∈ℕ−1,2 and S=1∪∪q∈m,k,naq|a≡1mod3,3≤a≤q. If m,k,n≡0mod3 and z≡1mod3, for some z∈m,k,n, then S is a dominating set of Cm,k,n and S=1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉.Proof.
Suppose thatm,k,n≡0mod3 and z≡1mod3, for some z∈m,k,n. Without loss of generality, we can assume that m≡1mod3. We will prove that S is a dominating set of Cm,k,n. There are four cases for k and n. We give the proof only for the case k≡1mod3 and n≡2mod3; the proofs of the other cases are similar. Let v∈VCm,k,n−S. If v=2q, for some q∈m,k,n, then there is 1∈S such that 1,v∈ECm,k,n. If v=uq, for some q∈m,k,n such that u≡0mod3, then u+1≡1mod3 and so u+1q∈S. Thus, there is u+1q∈S such that v,u+1q∈ECm,k,n. If v=uq, for some q∈m,k,n such that u≡2mod3 and u≠2, then u−1≡1mod3, and thus, u−1q∈S. Consequently, there is u−1q∈S such that v,u−1q∈ECm,k,n. If v=x, then there is mm∈S such that mm,v∈ECm,k,n. Therefore, S is a dominating set of Cm,k,n. It is easy to check that S=1+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.
The following lemmas aboutγ−set will be used in Theorem 1 to determine lower bounds of γCm,k,n.Lemma 11.
Letn,k,m∈ℕ−1,2 such that y≡0mod3, for all y∈m,k,n and z≡1mod3, for some z∈m,k,n, and let S be a γ−set of Cm,k,n. Then, the following hold:(1)
S∩1,x≤1.(2)
If1∈S, then qq∈S for some q∈m,k,n such that q≡1mod3.(3)
Ifx∈S, then 2q∈S for some q∈m,k,n such that q≡1mod3.Proof.
Without loss of generality, we can assume thatm≡1mod3.(1)
There are four cases fork and n. We give the proof only for the case k≡1mod3 and n≡2mod3; the proofs of the other cases are similar. On the contrary, suppose that S∩1,x=2. This gives 1,x∈S, and thus, every vertex in N1,x=1,2m,2k,2n,x,mm,kk,nn is dominated by S. Obviously, Cm,k,n−N1,x≅Pm−3∪Pk−3∪Pk−3 (see Figure 7).In order to dominate the vertices inCm,k,n−N1,x, then S−1,x must contain at least ⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉ vertices. This gives S≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉=2+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. From Lemma 10, we know that Cm,k,n contains a dominating set of order 1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. This contradicts the fact that S is a γ− set of Cm,k,n.(2)
Let1∈S. By (1), x∉S. Suppose, by contrary, qq∉S, for all q∈m,k,n such that q≡1mod3. In order to dominate x, then there exists zz∈S−1, for some z∈m,k,n such that z≠m and z≡2mod3. There are two cases for z. We give the proof only for the case z=n; the proof of the case z=k is similar. Since 1,nn∈S, every vertex in N1,nn=1,2m,2k,2n,n−1n,nn,x is dominated by S. It is clear that Cm,k,n−N1,nn≅Pm−2∪Pk−2∪Pn−4 (see Figure 8).In order to dominate the vertices inCm,k,n−N1,nn, then S−1,nn must contain at least ⌈m−2/3⌉+⌈k−2/3⌉+⌈n−4/3⌉ vertices. We thus get S≥2+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−4/3⌉=2+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. From Lemma 10, we know that Cm,k,n contains a dominating set of order 1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. This contradicts the fact that S is a γ− set of Cm,k,n.(3)
The proof is similar to that for 2.Figure 7
Cm,k,n−N1,x.Figure 8
Cm,k,n−N1,nn.Lemma 12.
Letn,k,m∈ℕ−1,2 and let S be a γ− set of Cm,k,n and S∩1,x=0. Then, the following hold:(1)
Ifm,k,n≡1mod3, then either 2m,mm∈S, 2k,kk∈S, or 2n,nn∈S.(2)
Ifm≡2mod3 and k,n≡1mod3, then 2m,mm∈S.(3)
Ifk≡2mod3 and m,n≡1mod3, then 2k,kk∈S.(4)
Ifn≡2mod3 and m,k≡1mod3, then 2n,nn∈S.Proof.
We give the proofs only for (1) and (2); the proofs of (3) and (4) are similar to that of (2).(1)
Letm,k,n≡1mod3. Suppose, by contrary, that neither 2m,mm∈S, 2k,kk∈S nor 2n,nn∈S. So, in order to dominate 1 and x, we get 2q,zz∈S for some q,z∈m,k,n such that q≠z. There are nine cases for q and z. We give the proof only for the case q=m and z=k; the proofs of the other cases are similar. Since 2m,kk∈S, every vertex in N2m,kk=1,2m,3m,k−1k,kk,x is dominated by S. We check at once that Cm,k,n−N2m,kk≅Pm−3∪Pk−3∪Pn−1 (see Figure 9).In order to dominate the vertices inCm,k,n−N2m,kk, then S−2m,kk must contain at least ⌈m−3/3⌉+⌈k−3/3⌉+⌈n−1/3⌉ vertices. This gives S≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−1/3⌉=2+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. From Lemma 10, we know that Cm,k,n contains a dominating set of order 1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. This contradicts the fact that S is a γ− set of Cm,k,n.(2)
Letm≡2mod3 and k,n≡1mod3. On the contrary, suppose that 2m,mm∉S. In order to dominate 1 and x, then 2q,zz∈S, for some q,z∈m,k,n such that q≠z or q=z∈k,n. If q≠z, then the proof is similar to that for 1. Let q=z∈k,n. There are two cases for q and z. We give the proof only for the case q=z=k; the proof of the case q=z=n is similar. Since 2k,kk∈S, every vertex in N2k,kk=1,2k,3k,k−1k,kk,x is dominated by S. If k≥5, then Cm,k,n−N2k,kk≅Pm−1∪Pk−5∪Pn−1 (see Figure 10).In order to dominate the vertices inCm,k,n−N2k,kk, then S−2k,kk must contain at least ⌈m−1/3⌉+⌈k−5/3⌉+⌈n−1/3⌉ vertices. We thus get S≥2+⌈m−1/3⌉+⌈k−5/3⌉+⌈n−1/3⌉=3+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. If k<5, then k=4. It is easily seen that Cm,k,n−N2k,kk≅Pm−1∪Pn−1. In order to dominate the vertices in Cm,k,n−N2k,kk, then S−2k,kk must contain at least ⌈m−1/3⌉+⌈n−1/3⌉ vertices. This gives S≥2+⌈m−1/3⌉+⌈n−1/3⌉=2+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. From Lemma 10, we know that Cm,k,n contains a dominating set of order 1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. This contradicts the fact that S is a γ− set of Cm,k,n.Figure 9
Cm,k,n−N2m,kk.Figure 10
Cm,k,n−N2k,kk.Lemma 13.
Letn,k,m∈ℕ−1,2 and let S be a γ− set of Cm,k,n. Then, S∩1,x=1 if one of the following holds:(1)
m≡1mod3 and k,n≡2mod3.(2)
k≡1mod3 and m,n≡2mod3.(3)
n≡1mod3 and m,k≡2mod3.Proof.
We give the proof only for the casem≡1mod3 and k,n≡2mod3; the proofs of the other cases are similar. Suppose, by contrary, that S∩1,x≠1. By Lemma 11 (1), S∩1,x=0. We thus get 1,x∉S. So, in order to dominate 1 and x, we get 2q,zz∈S, for some q,z∈m,k,n. There are two cases: q≠z and q=z. Following in a same manner as the proof of Lemma 12 (2), we can obtain S≥1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉, which contradicts the fact that S is a γ−set of Cm,k,n.Theorem 1.
Letn,k,m∈ℕ−1,2, D=m,k,n, and C=Cm,k,n. Then,(5)γC=2+m−33+k−33+n−33ify≡0mod3for somey∈Dorm,k,n≡2mod3,1+m−23+k−23+n−23ifm,k,n≡0mod3andy≡1mod3for somey∈D.Case 1.y≡0mod3, for some y∈D or m,k,n≡2mod3. By Lemma 9, γC≤2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉. We next prove that γC≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉. Let S be a γ−set of C.Case 1.1.y≡0mod3 for some y∈D. Without loss of generality, we can assume that m≡0mod3. In order to dominate 1 and x, there are sixteen cases, u,v∈S, for some u∈1,2m,2k,2n and v∈x,mm,kk,nn. We give the proofs only for the four cases 1,x∈S, 1,mm∈S, 2m,mm∈S, and 2m,kk∈S; the proofs of the other cases are similar.Case 1.1.1.1,x∈S. Then, every vertex in N1,x=1,2m,2k,2n,x,mm,kk,nn is dominated by S. Thus, C−N1,x≅Pm−3∪Pk−3∪Pk−3, so γC=S≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Case 1.1.2.1,mm∈S. It follows that every vertex in N1,mm=1,2m,2k,2n,m−1m,mm,x is dominated by S. If m≥4, then it is easy to check that C−N1,mm≅Pm−4∪Pk−2∪Pn−2. This gives S≥2+⌈m−4/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. For m=3, C−N1,mm≅Pk−2∪Pn−2. It follows that S≥2+⌈k−2/3⌉+⌈n−2/3⌉. Since m≡0mod3, γC=S≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Case 1.1.3.2m,mm∈S. Then, every vertex in N2m,mm=1,2m,3m,m−1m,mm,x is dominated by S. We can see that C−N2m,mm≅Pm−5∪Pk−1∪Pn−1 if m≥5, and C−N2m,mm≅Pk−1∪Pn−1 otherwise. It follows that S≥2+⌈m−5/3⌉+⌈k−1/3⌉+⌈n−1/3⌉ if m≥5, and S≥2+⌈k−1/3⌉+⌈n−1/3⌉ otherwise. Since m≡0mod3, γC=S≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Case 1.1.4.2m,kk∈S. We thus get every vertex in N2m,kk=1,2m,3m,k−1k,kk,x is dominated by S. Since C−N2m,kk≅Pm−3∪Pk−3∪Pn−1, γC=|S|≥2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Case 1.2.m,k,n≡2mod3. In order to dominate 1 and x, there are sixteen cases as above. In the same manner, we can prove that γC=2+⌈m−3/3⌉+⌈k−3/3⌉+⌈n−3/3⌉.Case 2.m,k,n≡0mod3 and y≡1mod3, for some y∈D. By Lemma 10, γC≤1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. We next show that γC≥1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. Without loss of generality, we can assume that m≡1mod3. Let S be a γ−set of C. By Lemma 11 (1), S∩1,x≤1. It follows that S∩1,x=1 or S∩1,x=0. Consider the following four cases.Case 2.1.k,n≡1mod3. If S∩1,x=1, then 1∈S or x∈S. We give the proof only for the case 1∈S; the proof of the case x∈S is similar. By Lemma 11 (2), mm∈S, kk∈S, or nn∈S. Here, we will give the proof only for the case mm∈S; the proofs of the other two cases are similar. Hence, 1,mm∈S. As in the proof of Case 1.1.2, γC=S≥2+⌈m−4/3⌉+⌈k−2/3⌉+⌈n−2/3⌉=1+⌈m−1/3⌉+⌈k−2/3⌉+⌈n−2/3⌉=1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. If S∩1,x=0, then 2m,mm∈S, 2k,kk∈S, or 2n,nn∈S by Lemma 12 (1). We give the proof only for the case 2m,mm∈S; the proofs of the other two cases are similar. As in the proof of Case 1.1.3, we get that if m≥5, then γC=|S|≥2+⌈m−5/3⌉+⌈k−1/3⌉+⌈n−1/3⌉=1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. If m≤4, then m=4. It follows that γC=|S|≥2+⌈k−1/3⌉+⌈n−1/3⌉=1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉.Case 2.2.k≡1mod3 and n≡2mod3. If S∩1,x=1, then 1∈S or x∈S. We give the proof only for the case 1∈S; the proof of the case x∈S is similar. By Lemma 11 (2), mm∈S or kk∈S. Here, we will give the proof only for the case mm∈S; the proof of the case kk∈S is similar. Hence, 1,mm∈S. As in the proof of Case 2.1, γC=S≥1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉. If S∩1,x=0, then 2n,nn∈S by Lemma 12 (4). Thus, every vertex in N2n,nn=1,2n,3n,n−1n,nn,x is dominated by S. It is clear that C−N2n,nn≅Pm−1∪Pk−1∪Pn−5 (see Figure 11). In order to dominate the vertices in C−N2n,nn, then S−2n,nn must contain at least ⌈m−1/3⌉+⌈k−1/3⌉+⌈n−5/3⌉ vertices. This gives S≥2+⌈m−1/3⌉+⌈k−1/3⌉+⌈n−5/3⌉=1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉.Case 2.3.k≡2mod3 and n≡1mod3. The proof is similar to that of Case 2.2.Case 2.4.k,n≡2mod3. By Lemma 13, S∩1,x=1. So, 1∈S or x∈S. We give the proof only for the case 1∈S; the proof of the case x∈S is similar. By Lemma 11 (2), mm∈S. Following in a same manner as the proof of Case 2.1, we can obtain γC=S≥1+⌈m−2/3⌉+⌈k−2/3⌉+⌈n−2/3⌉.Summarizing, we get the domination number of amalgamations of cycles at connected subgraphsCr⊲⊳CtH1≅fH2. From Lemmas 2‐7 and Theorem 1, we then get the following theorem.Figure 11
Cm,k,n−N2n,nn.Theorem 2.
Letr,s,t∈ℕ, 3≤r≤t, G=Cr⊲⊳CtH1≅fH2, and D=a,b,c where a=r−s+1, b=s−1, and c=t−s+1. Then(6)γC=r3ifH1≅Cr,r−33+t−33+1ifH1≅P1,r3+t−33ifH1≅P2andr≡0mod3andt≡0mod3,t+r−23ifH1≅P2andr≡0mod3ort≡0mod3,r+t−73+1ifH1≅P3andr>3,t−33+1ifH1≅Pr−1,r3+t−r−13ifH1≅Prandr≡0mod3andt≡1mod3,t3ifH1≅Prandr≡0mod3ort≡1mod3,2+a−33+b−33+c−33ifH1≅Ps,4≤s≤r−2,andy≡0mod3for somey∈Dora,b,c≡2mod3,1+a−23+b−23+c−23ifH1≅Ps,4≤s≤r−2,a,b,c≡0mod3,andy≡1mod3for somey∈D.



---

*Source: 7336728-2022-01-28.xml*