# A Note on the Signed Clique Domination Numbers of Graphs

Authors: Baogen Xu; Ting Lan; Mengmeng Zheng
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG=V,E be a graph. A function f:E⟶−1,+1 is said to be a signed clique dominating function (SCDF) of G if ∑e∈EKfe≥1 holds for every nontrivial clique K in G. The signed clique domination number of G is defined as γscl′G=min∑e∈EGfe|fis an SCDF ofG. In this paper, we investigate the signed clique domination numbers of join of graphs. We correct two wrong results reported by Ao et al. (2014) and Ao et al. (2015) and determine the exact values of the signed clique domination numbers of Pm∨Kn¯ and Cm∨Kn.


---

## Body

## 1. Introduction

We use Bondy and Murty [1] for terminology and notation not defined here and consider only simple and undirected graphs.The theory of domination is an important content in graphs, and its applications are more and more widely. In 1995, Dunbar et al. [2] first introduced the signed domination of graphs, and now, there are a lot of variations, such as the total domination [3]. However, most of them belong to the vertex domination of graphs, and a few of the edge dominations were studied. In 2001, B. Xu puts forward the signed edge domination of graphs [4]. Since then, many variations based on edge domination have become more and more abundant, such as signed total domination [5], Roman domination [6], signed cycle domination [7], and signed clique domination [8]. The emergence of these concepts enriched and completed the domination theory of graphs. In this paper, we consider the signed clique domination numbers of joint graphs.LetG=V,E be a graph with vertex set V=VG and edge set E=EG. Every maximal complete subgraph K of graph G is called a clique of G; that is, there are no other complete subgraphs contain K. A clique K is called nontrivial if K≠K1.Given a graphG=V,E, for any vertex v∈V, let Ev be the set of edges in G incident to v. If A⊆V, B⊆V, and A∩B=∅, then we write EA,B=uv∈E|u∈A,v∈B.For any two disjoint graphsG1 and G2, then G1∨G2 denotes the joint graph of G1 and G2, where(1)VG1∨G2=VG1∪VG2,EG1∨G2=EG1∪EG2∪uv|u∈VG1,v∈VG2.For ease of description, letG=V,E be a graph, S⊆E and f:E⟶R be a real-valued function defined on E, then we put fS=∑e∈Sfe.Definition 1 (see [8]).
LetG=V,E be a graph, a function f:E⟶−1,+1 is said to be a signed clique dominating function (SCDF) of G if fEK≥1 holds for every nontrivial clique K in G. The signed clique domination number of G is defined as(2)γscl′G=minfE|fis an SCDF ofG.
Iff is an SCDF such that γscl′G=fEG, then the function f is said to be a minimum SCDF of G.Lemma 1 (see [8]).
For any graphG, γscl′G≡EGmod2.Lemma 2 (see [8]).
For any connected graphG of order n, if EG=m and ωG≤4. Then,(3)γscl′G≥2n−m−2.This lower bound is the best possible.For the joint graphs of the two graphs, we have the following results.Lemma 3 (see [9]).
(1) For any two positive integersm≥3 and n≥2, then(4)γscl′Cm∨nK2=3−n,whenm=3,m+n,whenm≥4.
(2) For any two positive integersm≥4 and n≥4, then(5)γscl′Cm∨Cn=m+n+1,whenmandnare odd,m+n,otherwise.Lemma 4 (see [10]).
For any positive integern>i>3, then(6)γscl′Ci∨Kn−i¯=6−n,wheni=3,i,wheni≥4andi≡0mod2,n−2,wheni≥4andi≡1mod2.However, we find the following two lemmas are wrong.Lemma 5 (see [10]).
For any positive integern>i>0, then(7)γscl′Pi∨Kn−i¯=n−1,wheni=1,⌊i2⌋−⌈i2⌉n−i+i−1,wheni≥2.For example, in fact, whenn=6 and i=5, then γscl′P5∨K1¯≤1. The labeling of P5∨K1¯ is shown in Figure 1, and when n=8 and i=6, then γscl′P6∨K2¯≤3. The labeling of P6∨K2¯ is shown in Figure 2 where unlabeled edges are assigned as -1.Figure 1
P5∨K1¯.Figure 2
P6∨K2¯.Lemma 6 (see [11]).
For any positive integerm≥3 and n≥3, then(8)γscl′Kn∨Cm=26−n⌈m2⌉−n+1m+nn−12,whenn=3,4,5,−n+1m+2n+2+−1⌊n/2⌋+1+12,whenn≥6.In fact, the above conclusion is not true forn=3or4, and m is odd. For example, we may see γscl′K3∨C5≤−1 and γscl′K4∨C5≤−9. The labeling of K3∨C5 and K4∨C5 is shown in Figures 3 and 4, respectively, where unlabeled edges are assigned as –1.In this note, we mainly correct two wrong conclusions in [10, 11] and determine exactly the signed clique domination numbers of Pm∨Kn¯ and Cm∨Kn.Figure 3
K3∨C5.Figure 4
K4∨C5.


## 2. Main Results

Theorem 1.
For any two positive integersm≥2 and n≥1, then(9)γscl′Pm∨Kn¯=1,whenm=2orn=1,m−n−1,whenm≥3andmis odd,m−3,whenm≥4andmis even.Proof.
LetG=Pm∨Kn¯ be a joint graph, VG=VPm∪VKn¯, we define A=VPm=u1,u2,…,um, EPm=uiui+1|1≤i≤m−1, B=VKn¯=v1,v2,…,vn.Case 1.
Whenm=2.
Letf be a minimum SCDF of G, that is, γscl′G=fEG. Obviously, there are n cliques Kj=K31≤j≤n in G, among Kj is a clique with three vertices u1,u2,vj. The n cliques contain a common edge u1u2. According to Definition 1, we have fEKj≥1 held for every clique Kj. Then, we obtain ∑j=1nfEKj≥n. In this inequality, note that the function value fe of each edge e in EP2 is counted exactly n times, and the function value fe of each edge e in EA,B is counted one time. Then,(10)nfEP2+fEA,B≥n.
For every vertexvj∈B, Evj is the set of edges in G incident to vj. It is obvious that fEvj≥0 (otherwise, if there exists a vertex vs such that fEvs<0). It implies the contradiction that fEKs<0). Thus, we derive fEA,B=∑j=1nfEvj≥0. Combining with (10), we have(11)γscl′G=fEG,=fEP2+fEA,B≥1+n−1nfEA,B≥1.
Meanwhile, we define such a functionf′ of G as follows:(12)f′e=−1,e=u1vj1≤j≤n,+1,otherwise.
It is routine to check thatf′ is an SCDF of G. Hence,(13)γscl′G≤f′EG=f′EP2+f′EA,B=1.
Combining withγscl′G≥1, we finally derive γscl′G=1.Case 2.
Whenn=1.
We know thatG=Pm∨K1 is connected graph of order m+1, EG=2m−1, and wG≤3. By Lemma 2, we have γscl′G≥2m+1−2m−1−2=1. Meanwhile, we define such a function f of G as follows:(14)fe=+1,e∈EA,B,−1,e∈EPm.
It is routine to check thatf is an SCDF of G. Then,(15)γscl′G≤fEG=fEPm+fEA,B=1.
Combining withγscl′G≥1, we finally have γscl′G=1.Case 3.
Whenm≥3 and m is odd.
Letf be a minimum SCDF of G, that is, γscl′G=fEG. Clearly, there are nm−1 cliques Ki,j=K31≤i≤m−1,1≤j≤n in G, among Ki,j is a clique with three vertices ui,ui+1,vj. According to Definition 1, we obtain fEKi,j≥1holds for every clique Ki,j. Therefore, we have ∑i=1m−1∑j=1nfEKi,j≥nm−1.
In the above inequality, we know that the function valuefe of each edge e in EPm is counted exactly n times. Then, let E1 be the edge set in EA,B where the function value fe of each edge e is counted one time, and E2 is the edge set in EA,B where the function value fe of each edge e is counted exactly 2 times, where(16)E1=uivj|i=1,m,1≤j≤n,E2=uivj|2≤i≤m−1,1≤j≤n.
Then,(17)∑​m−1i=1∑​nj=1fEKi,j=nfEPm+fE1+2fE2≥nm−1.
For every vertexvj∈B, it is obvious that fEvj≥−1 (otherwise, there must exist a clique Ks,t1≤s≤m−1,1≤t≤n such that fEKs,t<1, a contradiction). Then, we have fE1+E2=∑j=1nfEvj≥−n. We assume that there are k vertices vj1≤j≤n such that ∑i=2m−1fuivj≥1, then(18)2n−4k≤fE1≤2n,2k−n≤fE2≤km−2−n−k,where 0≤k≤n.
According to (17), we obtain(19)γscl′G=fEPm+fE1+fE2≥m−1+n−1nfE1+n−2nfE2≥m−1+n−1n2n−4k+n−2n2k−n=m−1+n−2k≥m−n−1.
Meanwhile, we define such a functionf′ of G as follows:(20)f′e=−1i,e=uivj1≤i≤m,1≤j≤n,+1,e∈EPm.
It is clear thatf′ is an SCDF of G. Therefore,(21)γscl′G≤f′EG=f′EPm+f′E1+f′E2=m−n−1.
Together withγscl′G≥m−n−1, we have γscl′G=m−n−1.Case 4.
Whenm≥4 and m is even.
Letf be a minimum SCDF of G, i.e., γscl′G=fEG. The same as Case 3, we have fEvj≥0, then fE1+fE2=∑j=1nfEvj≥0. We assume that there are k vertices vj1≤j≤n such that ∑i=2m−1fuivj≥2, then(22)−2k≤fE1≤2n,2k≤fE2≤km−2,where 0≤k≤n.
According to (17), we have(23)γscl′G=fEPm+fE1+fE2≥m−1+n−1nfE1+n−2nfE2≥m−1+n−1n−2k+n−2n2k=m−1−2kn≥m−3.
In addition, we define such a functionf′ of G as follows:(24)f′e=−1,e∈u1vj∪u2u31≤j≤n,−1i+1,e=uivj3≤i≤m,1≤j≤n,+1,otherwise.
It is routine to check thatf′ is an SCDF of G. Therefore,(25)γscl′G≤f′EG=f′EPm+f′E1+f′E2=m−3.
Combining withγscl′G≥m−3, we have γscl′G=m−3. This completes the proof of Theorem 1.Theorem 2.
For any two positive integersm≥3 and n≥3, then(26)γscl′Cm∨Kn=3−2m+2m2,whenn=3;6−3m,whenn=4;10−6m+2m2,whenn=5;−n+1m+2n+2+−1⌊n/2⌋+1+12,whenn≥6.Proof.
LetG=Cm∨Kn, A=VCm=u1,u2,…,um, and ECm=uiui+1|1≤i≤m, among um+1=u1; B=VKn=v1,v2,…,vn, EG=nn−1/2+mn+1.
Letf be a minimum SCDF of G, that is, γscl′G=fEG. Obviously, there are m cliques Ki=Kn+21≤i≤m in G, among Ki is a clique with n+2 vertices ui,ui+1 and the vertex set B.Case 5.
Whenn=3. Note that Ki=K51≤i≤m. According to Definition 1, we have fEKi≥1 held for every clique Ki. Since EK5=10, by Lemma 1, we have fEKi≥2. Then, we obtain ∑i=1mfEKi≥2m. In this inequality, we know that the function value fe of each edge e in EK3 is counted exactly m times, the function value fe of each edge e in ECm is counted exactly one time, and the function value fe of each edge e in EA,B is counted 2 times. Then,(27)mfEK3+fECm+2fEA,B≥2m.
SincefEK3≤3, we have(28)fECm+2fEA,B≥−m.
According to (27), we obtain(29)γscl′G=fEK3+fECm+fEA,B≥2+m−1mfECm+m−2mfEA,B.
Together with (28), we have(i)
WhenfEA,B≥0,(30)γscl′G≥2+m−1mfECm+m−2mfEA,B≥2+m−1m⋅−m+0=3−m.(ii)
WhenfEA,B≤0,(31)γscl′G≥2+m−1mfECm+m−2mfEA,B=2+m−1mfECm+2fEA,B−fEA,B≥2+m−1m⋅−m−0=3−m.
Then, we haveγscl′G≥3−m. Note that, when m is odd, EG=4m+3 is also odd. As per Lemma 1, we derive γscl′G≥4−m. Thus, γscl′G≥3−2m+2⌈m/2⌉. In addition, we define such a function f′ of G as follows:(32)f′e=+1,e∈EK3∪uivj|1≤i≤m,j=1∪uivj|i≡1mod2,j=2,−1,otherwise.
It is not difficult to check thatf′ is an SCDF of G, then γscl′G≤f′EG=3−2m+2⌈m/2⌉. In summary, when n=3, γscl′G=3−2m+2⌈m/2⌉.Case 6.
Whenn=4. We know Ki=K61≤i≤m. By the Definition 1, we have fEKi≥1 held for every clique Ki. Then, we obtain ∑i=1mfEKi≥m. The same as Case 5, we have(33)mfEK4+fECm+2fEA,B≥m.
SincefEK4≤6, we derive(34)fECm+2fEA,B≥−5m.
According to (33), we have(35)γscl′G=fEK4+fECm+fEA,B≥1+m−1mfECm+m−2mfEA,B.
Combining with (34), we have(i)
WhenfEA,B≥−2m,(36)γscl′G≥1+m−1mfECm+m−2mfEA,B≥1+m−1m⋅−m+m−2m⋅−2m=6−3m.(ii)
WhenfEA,B≤−2m,(37)γscl′G≥1+m−1mfECm+m−2mfEA,B=1+m−1mfECm+2fEA,B−fEA,B≥1+m−1m⋅−5m+2m=6−3m.
Then, we haveγscl′G≥6−3m. Meanwhile, we define such a function f′ of G as follows:(38)f′e=+1,e∈EK4∪uivj|1≤i≤m,j=1,−1,otherwise.
Clearly,f′ is an SCDF of G, and then γscl′G≤f′EG=6−3m. In summary, when n=4, whether m is odd or m is even, we finally have γscl′G=6−3m.Case 7.
Whenn=5. We know Ki=K71≤i≤m. As per Definition 1, we have fEKi≥1 held for every clique Ki. Then, we obtain ∑i=1mfEKi≥m. The same as Case 5, we have(39)mfEK5+fECm+2fEA,B≥m.
SincefEK5≤10, we derive(40)fECm+2fEA,B≥−9m.
According to (39), we have(41)γscl′G=fEK5+fECm+fEA,B≥1+m−1mfECm+m−2mfEA,B.
Combining with (40), we have(i)
WhenfEA,B≥−4m,(42)γscl′G≥1+m−1mfECm+m−2mfEA,B≥1+m−1m⋅−m+m−2m⋅−4m=10−5m.(ii)
WhenfEA,B≤−4m,(43)γscl′G≥1+m−1mfECm+m−2mfEA,B=1+m−1mfECm+2fEA,B−fEA,B≥1+m−1m⋅−9m+4m=10−5m.
Then, we haveγscl′G≥10−5m. Notice that when m is odd, EG=6m+10 is even. By Lemma 1, we obtain γscl′G≥11−5m. Thus, γscl′G≥10−6m+2⌈m/2⌉. In addition, we define such a function f′ of G as follows:(44)f′e=+1,e∈EK5∪uivj|i≡1mod2,j=1,−1,otherwise.
It is not difficult to check thatf′ is an SCDF of G, then γscl′G≤f′EG=10−6m+2⌈m/2⌉. In summary, when n=5, we have γscl′G=10−6m+2⌈m/2⌉.Case 8.
Whenn≥6. Let f be a minimum SCDF of G, that is, γscl′G=fEG. Write s=e∈EG|fe=1, s1=e∈EKn+2|fe=1.
According to Definition1, we have fEKn+2≥1 held for every clique Kn+2 in G. Thus, we have s1≥⌊n+2n+1/4⌋+1. It implies s≥s1≥⌊n+2n+1/4⌋+1, and then,(45)γscl′G=2s−EG≥−n+1m+2n+2+−1⌊n/2⌋+1+12.
In addition, sincen≥6, we know nn−1/2≥⌊n+2n+1/4⌋+1. Now define a function f′, that is, let the number of +1 edges in Kn is ⌊n+2n+1/4⌋+1, the other edges are assigned as -1. It is obvious that(46)γscl′G≤f′EG=−n+1m+2n+2+−1⌊n/2⌋+1+12.
In summary, whenn≥6, we have γscl'G=−n+1m+2n+2+−1⌊n/2⌋+1+1/2. We complete the proof of Theorem 2.



---

*Source: 3208164-2022-09-17.xml*