# On the Connected Safe Number of Some Classes of Graphs

Authors: Rakib Iqbal; Muhammad Shoaib Sardar; Dalal Alrowaili; Sohail Zafar; Imran Siddique
Journal: Journal of Mathematics
 (2021)

---

## Abstract

For a connected simple graphG, a nonempty subset S of VG is a connected safe set if the induced subgraph GS is connected and the inequality S≥D satisfies for each connected component D of G∖S whenever an edge of G exists between S and D. A connected safe set of a connected graph G with minimum cardinality is called the minimum connected safe set and that minimum cardinality is called the connected safe numbers. We study connected safe sets with minimal cardinality of the ladder, sunlet, and wheel graphs.


---

## Body

## 1. Introduction

A facility location problem (FLP) means to place and manage a certain facility in such a way as to get or achieve the maximum objective with minimizing cost. For further study of FLPs, we refer to the literature of combinatorial optimization [1]. Fujita et al. [2] studied the FLP and proposed a notion of a safe set of graphs.We refer to [3] for terminology and notation not explained here. Throughout the paper, we will consider only simple and connected graphs. Let G be a graph with VG and EG as its vertex and edge set, respectively. The number of vertices in a graph G is the order of G. For v∈VG, Nv=u∈VG:uis adjacent tov and Nv=Nv∪v is called open and closed neighborhood of v in G, respectively. For v∈VG, the degree of vertex v is defined as degv=Nv. For subset S⊂VG, GS denotes the subgraph induced by S. For subset X⊂VG, if G∖X is disconnected, then X is known as vertex cut. The vertex connectivity denoted by κG is defined as minX:Xis vertex cut. Let CG denote the set of all connected components of G.SupposeA and B are disjoint subgraphs of G; then, the set of edges of EG that joins some vertices of A and B is denoted by EA,B. A nonempty subset S of VG is a safe set if, for each X∈CG∖S and each Y∈CGS, the inequality Y≥X holds whenever EX,Y≠∅. If GS is connected, then S is known as a connected safe set. For any graph G, sG=minS:Sis a safe set ofG and csG=minS:Sis a connected safe set ofG are known as the safe number and connected safe number, respectively. It is clear from the definition that sPn=csPn=⌈n/3⌉ and sCn=csCn=⌈n/2⌉, where Pn and Cn are the path and cycle of order n, respectively. Fujita et al. [2] proved that for any graph G, sG≤csG≤2sG−1.In general, there is no algorithm available to compute a safe number and a connected safe number of a graphG. It was shown in [2] that the computation of safe number and connected safe number is an NP-complete problem. But, on the contrary, Fujita et al. [2] show that csG can be computed in linear time in case of trees. Also, Árueda et al. [4] show that sG can be computed in On5 time on trees. Any tree T with one vertex of degree not more than 3 holds that sT=csT. Motivated by this equality, for the Cartesian product of two complete graphs, say G, Kang et al. [5] proved that the safe number sG and connected safe number csG are also the same.For a vertex-weighted graph, Bapat et al. [6] presented the weighted safe set problem by considering the graph as a community network. For further study about the weighted safe set, we refer to [7–9]. Furthermore, the study on safe set and weighted safe set was conducted by several authors. The parameterized complexity of safe set problems was investigated by Belmonte et al. [10]. Macambiraa et al. [11] presented a mixed integer linear programming formulation and an algorithm for both the weighted safe set and the safe set problems. Fujita and Furuya [12] investigated the comparison between integrity and the safe number of graphs.In this paper, we describe the connected safe set and compute the connected safe number of ladder, wheel, and sunlet graphs, respectively. The paper is concluded in Section5.


## 2. Safe Set of the Ladder Graph

For convenience, we consider the ladder graphG of order n≥4 with vertex set VG=v1,v2,…,vn labeled as shown in Figure 1 [13].Figure 1
The ladder graphG.Theorem 1.
LetG be a ladder graph; then, the connected safe set is(1)S=vn/8+2,vn/8+3,…,vn/8+n/4+1,vn−n/8−n/4,vn−n/8−1,ifn≡0,2,6mod8,vn/8+2,vn/8+3,…,vn/8+n/4,vn−n/8−n/4+1,vn−n/8−1,otherwise.Proof 1.
The proof is divided into two cases:Case 1: assume thatn≡0,2,6mod8. Let S=vn/8+2,vn/8+3,…,vn/8+n/4+1,vn−n/8−n/4,vn−n/8−1 be a subset of VG. Clearly, v1vn,v2vn−1,…,vn/2vn/2−1∈EG. Hence, vn/8+2 and vn−n/8−1 as well as vn/8+n/4+1 and vn−n/8−n/4 are adjacent. Therefore, GS is connected. Now, CG∖S=D1,D2,D3, where D1=vn−n/8−n/4+1,vn−n/8−n/4+2,…,vn−n/8−2, D2vn/8+n/4+2,vn/8+n/4+3,…,vn−n/8−n/4−1, and D3=v1,v2,…,vn/8+1,vn−n/8,…,vn−1,vn. It is easy to see that S=n/4+2, D1=n/4−2, D2=n−2n/8−2n/4−2, and D3=2n/8+2. This implies Di≤S and EDi,S≠∅ for 1≤i≤3. Hence, both the conditions of connected safe set are satisfied.Case 2: the similar arguments might work for the other case.Theorem 2.
For a ladder graphG of order n, the following holds:(2)csG=n3,if4≤n≤8,n4+2,ifn≥10andn≡0,2,6mod8,n4+1,otherwise.Proof 2.
Assume thatS is a connected safe set of cardinality csG and CG∖S=D1,D2,…,Dt, ordered so that D1≤D2≤⋯≤Dt.
Ift=1, then either v1,vn∈S or vn/2,vn/2+1∈S. We assume that v1,vn∈S. Let u∈D1 such that Eu,S≠∅. Then, by removing vertex v1 from S and adding vertex u in S, we get a connected safe set S∗ and for S∗, D1<maxD|D∈CG∖S∗, which is a contradiction. Hence, t≥2.
Consider thatn≥10 and n≡0,2,6mod8.
We want to show thatS=n/4+2. Suppose on the contrary S=n/4+1 since κG=2.
LetX=vi,vj|vi,vj∈VGandi+j=n+1 be the vertex cut sets, where 1<i<n/2 and n/2<j<n and clearly X=n/2−2. We assume that S contains Xl, where l≥2. Suppose, for contradictions l=1, clearly t=2. Let w be a vertex of D2 such that EX1,w=∅ and ES,w≠∅. Then, there exists a vertex x of S such that we have the following:(i)
S−x is connected(ii)
X1∩x=∅(iii)
Ew,x=∅
Then, by removing vertexx from S and adding vertex w in S, we get a connected safe set S∗ and for S∗, we have D1<maxD|D∈CG∖S∗, which is a contradiction. Hence, l≥2. It is sufficient to show for X1 and X2 that S=csG. Note that if EX1,X2≠∅, then t=2. Hence, we assume that EX1,X2=∅. Suppose that vi1,vi2∈S such that Evi1,X1≠∅ and Evi2,X2≠∅ since S is connected. Therefore, half vertices between X1 and X2 belong to S and the other half belongs to a component of G∖S (say D1). This implies D1≤S−4=n/4−3. Note that D2≤D3. Thus, D3≥n−S−D1/2=n−2n/4+2/2≥S, a contradiction. Hence, S=n/4+2.
The similar arguments might work for other cases.


## 3. Safe Set of the Wheel Graph

For convenience, we consider the wheel graphG of order n≥4 with vertex set VG=v1,v2,…,vn labeled as shown in Figure 2 [14].Figure 2
The wheel graphG.Theorem 3.
LetG be a wheel graph. Then,(3)S=v1,v1+k,v1+2k,…,v1+k−3k,v1+k−4k,vj,vn,where(4)vj=vn−1,if2+k−3k≥n,v1+k−3k,otherwise,where k=⌈n⌉+1 and 1+k−4k<j<n.Proof 3.
LetS=v1,v1+k,v1+2k,…,v1+k−3k,v1+k−4k,vj,vn be a subset of VG. Since degvn=n−1, this implies GS is connected. Therefore, CG∖S=D1,D2,…,Dl, where D1=v2,v3,…,vk, D2=v2+k,v3+k,…,v2k, …, Dl−2=v2+k−5k,v3+k−5k,…,vk−4k, Dl−1=v2+k−4k,v3+k−4k,…,vj−1, and Dl=vj+1,vj+2,…,vn−1. Now, Di=k−1=⌈n⌉=S for all 1≤i≤l−2. Hence, we have two cases:Case 1: let2+k−3k≥n; then, vj=vn−1; this implies Dl=∅. Hence, Dl−1=v2+k−4k,v3+k−4k,…,vn−2 and Dl−1=n−k−4k−3=n−⌈n⌉2+2⌈n⌉−3.Case 2: let2+k−3k<n; then, vj=v1+k−3k; this implies Dl−1=, v2+k−4k,v3+k−4k,…,vk−3k and Dl=v2+k−3k,v3+k−3k,…,vn−1. Therefore, Dl−1=k−1 and Dl=n−k−3k−2=n−⌈n⌉2+⌈n⌉.
It is clear from both the cases thatDi≤S for all i=1,2,…,l. Thus, S is a connected safe set.Theorem 4.
For a wheel graphG, the following holds:(5)csG=n,where n is the order of G.Proof 4.
LetS be the connected safe set of size csG; then, CG∖S=D1,D2,…,Dt, ordered so that D1≤D2≤…≤Dt.
Note thatvn∈VG is a vertex such that degv=n−1. If t=1, then we have the following two cases:Case 1: ifvn∉S, then S⊂VG−vn. Since S is connected, VG−vn is the cycle. Then, clearly GS is a path. Let u∈S such that degu=2 in GS. Then, by removing vertex u from S and adding vertex vn in S, we get a connected safe set S∗ for S∗D1<maxD|D∈CG∖S∗.Case 2: ifvn∈S, then a vertex u exists in S for which Eu,D1=∅. Let y be a vertex of D1 such that Ey,S≠∅. Then, by removing vertex u from S and adding vertex y in S, we get a connected safe set S∗ and for S∗ and we have D1<maxD|D∈CG∖S∗.
Both cases show contradiction. Hence,t≥2.
If we chooseS in such a way that for all x′,y′∈S, x′y′∉EGS−vn, then t=S−2. Note that this is the most possible case of choosing the connected safe set S for which G∖S has maximum components. As a result, we have 2≤t≤S−2.
We want to prove thatcsG=⌈n⌉. On the contrary, assume that csG=⌈n⌉−1. Note that t=⌈n⌉−2. We assume that Di=S for all 1≤i≤t, so VG=∑i=1tDi+S=⌈n⌉−2⌈n⌉−1+⌈n⌉−1=⌈n⌉−12<n, a contradiction, and consequently, the cardinality of at least one component of G∖S must be greater than S, which is impossible. Hence, csG=⌈n⌉.


## 4. Safe Set of the Sunlet Graph

For convenience, we considered the sunlet graphG of order n≥6 with vertex set VG=v1,v2,…,vn labeled as shown in Figure 3 [15].Figure 3
The sunlet graphG.Theorem 5.
LetG be a sunlet graph of order n≥6 and S be the connected safe set; then,(6)S=v2,v4,…,v2n/3.Proof 5.
Suppose thatS=v2,v4,…,v2n/3 is a subset of VG such that GS is its induced subgraph. For vi,vi+2∈S, Nvi∩Nvi+2=vi,vi+2, where i=2,4,…,2n/3−2. Hence GS is connected.
We want to show thatS is a connected safe set. Thus, CG∖S=D1,D2,…,Dt, where D1=v1,D2=v3,…,Dt−1=v2n/3−1 and Dt=v2n/3+1,v2n/3+2,…,vn. Note that Dj|<|S for all 1≤j≤t−1. Now, Dt=n−2n/3≤S. Hence, S is a connected safe set.Theorem 6.
For a sunlet graphG of order n≥6, the following holds:(7)csG=n3.Proof 6.
Assume thatS is a connected safe set of cardinality csG; then, CG∖S=D1,D2,…,Dt, ordered such that D1≤D2≤…≤Dk.
Ift=1, then S=X∪Y, where X=v|v∈Sand degv=3 and Y=u|u∈Sand degv=1. Note that S−v is disconnected for all v∈X. Let u∈Y and w∈D1 such that Ew,S≠∅; then, S∗=S−u∪w is a connected safe set and for S∗, D1<maxD|D∈CG∖S∗, a contradiction. Thus, t≥2.
LetZ⊂VG such that Z∩S=∅, ES,Z≠∅, and GZ is a path. Note that S′=S−Y∪Z is a connected safe set; then, obviously GS is the path, and for that choice of the connected safe set, we have CG∖S′=MaxCG∖S|Sis a connected safe set. As a result, 2≤t≤S+1.
Suppose on the contrary thatcsG=n/3−1. Since 2≤t≤|S|+1, d=∑i=1k−1Di≤S and n−2n/3+2≥VG−S−d=Dk>S, a contradiction. Hence, csG=n/3.


## 5. Conclusion

In this article, the connected safe set and connected safe number of ladder, wheel, and sunlet graphs are studied. The computation of connected safe number is an NP-complete problem and is known for few classes of graphs. A nontrivial graph of ordern whose degree set consists of n−1 elements is called an antiregular graph. Hence, in the future, it is interesting to study the safe set number for some other standard classes of graphs such as regular graphs, antiregular graphs, and well-known computer networks.



---

*Source: 9483892-2021-10-23.xml*