# An Upper Bound on the Radius of a 3-Vertex-ConnectedC4-Free Graph

Authors: Blessings T. Fundikwa; Jaya P. Mazorodze; Simon Mukwembi
Journal: Journal of Mathematics
 (2020)

---

## Abstract

We show that ifG is a 3-vertex-connected C4-free graph of order n and radius r, then the inequality r≤2n/9+O1 holds. Moreover, graphs are constructed to show that the bounds are asymptotically sharp.


---

## Body

## 1. Introduction

LetG=V,E be a finite, connected, undirected graph with vertex set V and edge set E. The distance dGu,v between two vertices u,v of G is the length of a shortest u-v path in G. The eccentricity ecv of a vertex v∈V is the maximum distance between v and any other vertex in G. The value of the minimum eccentricity of the vertices of G is called the radius of G denoted by radG. The degree degv of a vertex v of G is the number of edges incident with v. The minimum degree δG is the minimum of the degrees of vertices in G. The open neighbourhood Nv of a vertex v is the set of all vertices of G adjacent to v. The closed neighbourhood Nv of v is the set Nv∪v. A graph is triangle-free if it does not contain C3 as a subgraph and C4−free if it does not contain C4 as a subgraph. For notions not defined, here we refer the reader to [1].In our research, we are concerned with upper bounds on radius in terms of order and each of the three classical connectivity measures, namely, minimum degree, edge-connectivity, and vertex-connectivity for general graphs and for graphs with forbidden subgraphs such asC3 and C4. Several upper bounds on radius in terms of other graph parameters are known. For example, Erdős et al. [2] and independently Dankelmann et al. [3] proved that if G is a connected graph of order n and minimum degree δ≥2, then(1)radG≤3n2δ+1+O1.Erdős et al. [2] proved that if G is a connected triangle-free graph of order n and minimum degree δ≥2, then(2)radG≤n−2δ+12,and that if G is a connected C4-free graph of order n and minimum degree δ≥2, then(3)radG≤5n2δ2−2δ/2+1.Bounds on the radius in terms of order and edge-connectivity were given by Dankelmann et al. [4]. They showed that if λ=3, then(4)radG≤n3+173,and they constructed graphs that, apart from the additive constant, attain the bound. Mukwembi, in [5], showed that if G is a triangle-free 3-edge-connected graph, then(5)radG≤3n10+565,and constructed graphs that, apart from the additive constant, attain the bound. Bounds on the radius in terms of order and vertex-connectivity were given by Harant and Walther [6]. If κG is even, then the well-known bound, diamG≤n+κG−2/κG, on the diameter is also sharp for the radius. For odd κG, Harant and Walther [6] showed that(6)radG≤nκG+1+Ologn.In [7], Harant showed that for κ=3, the Ologn term can be replaced by a constant. It is worth noting that, while it has not been formally communicated, the bounds on the radius of triangle-free graphs with respect to order and vertex-connectivity are exactly the same as those for graphs without restrictions where subgraphs are concerned. To date, there are no known bounds reported on the radius of C4-free graphs with respect to order and vertex-connectivity. The main theorem of this paper seeks to prove the following:Theorem 1.
LetG be a 3-vertex-connected C4-free graph of order n. Then, radG≤2n/9+263/9.To show that this bound is asymptotically sharp, consider the graphCkS where S is the graph in Figure 1 and CkS is the graph formed by replacing each vertex of a Ck-cycle by the graph S and replacing an edge between consecutive vertices in the cycle by an edge connecting y to v and another edge connecting x to u, and this is between the two copies of S that have replaced consecutive vertices in Ck. As an example, consider C4S in Figure 2. Note that CkS is a 3-vertex-connected C4-free graph and that whenever k≡0mod2, we have(7)radCkS=2n9.Figure 1
The graph S.Figure 2
C4S.


## 2. Results

LetG be a 3-vertex-connected, C4-free graph, of order n, and z be a fixed centre vertex of G, so that radG=r=ecz. For each i=0,1,2,…,r, let Ni:=v∈VGdGv,z=i and ki=Ni. Note that for each i with 1≤i≤r−1 and any v∈Ni, we have Nv⊆Ni−1∪Ni∪Ni+1. We employ the notation N≤j=∪0≤i≤jNi and N≥j=∪j≤i≤rNi. Since Nr≠∅, from now onwards fix a vertex zr∈Nr. Form a spanning tree T of G that is distance preserving from z. For a vertex y∈VG, denote by Tz,y, the path connecting z and y in T. We say y is related to zr if there exist vertices u,v∈VG where u∈VTz,zr∩N≥37 and v∈VTz,y∩N≥37 such that dGu,v≤18.Lemma 1.
Letr≥73 and z,zr as above. Then, there exists a vertex in N≥r−37 which is not related to zr.Proof.
Suppose to the contrary that every vertexy∈N≥r−37 is related to zr. Let z37 be the vertex of Tz,zr which belongs to N37. Then, for any x∈N≤r−38, we have dGz37,x≤dGz37,z+dGz,x≤37+r−38=r−1. Since every vertex in N≥r−37 is related to zr, for any x∈N≥r−37, there exist u,v, where u∈VTz,zr∩N≥37 and v∈VTz,x∩N≥37 such that dGu,v≤18. Thus, dGz37,x≤dGz37,u+dGu,v+dGv,x≤dGz,u−37+18+r−dGz,v≤r−19+dGu,v≤r−1, for any x∈N≥r−37. Hence, ecz19≤r−1, contradicting the fact that radG=r.
Throughout the rest of this paper,yt is a fixed vertex in N≥r−37 which is not related to zr. Let Tz,zr=zx1x2…xr−1zr (respectively, Tz,yt=zy1y2…yt−1yt) be a path from z to zr (respectively, yt) in T. For each i with 0≤i≤r (0≤i≤r−37) denote by Xid (Yid), d∈0,1,2,3,4,5,6,7,8,9, the set of all vertices in Ni whose distance from VTz,zr∩N≥37 (VTz,yt∩N≥37) is at most d in G. Thus, for example, Xi3⊆Xi4. For each i with 0≤i≤r (0≤i≤r−37) denoted by Xie (Yie), e∈1,2,3,4,5,6,7,8,9, the set of all vertices in Ni whose distance from VTz,zr∩N≥37 (VTz,yt∩N≥37) is exactly e in G. Thus, for example, Xi3=Xi0⊎Xi1⊎Xi2⊎Xi3. For each i with 0≤i≤r (0≤i≤r−37) denoted by Xid,e (Yid,e), d,e∈1,2,3,4,5,6,7,8,9, the set of all vertices in Ni whose distance from VTz,zr∩N≥37 (VTz,yt∩N≥37) is f where d≤f≤e in G. Thus, for example, Xi1,3=Xi1⊎Xi2⊎Xi3. For each d∈2,3 denoted by Q≤da, the set of all vertices in G whose distance from a∈VG is at most d in G. Thus, for example, Q≤2a⊆Q≤3a. The following fact follows from the fact that yt is not related to zr:Fact 1.
∪i=37r−37Xi9∩∪i=37r−37Yi9=∅.Lemma 2.
Letr≥81. With the above notation, for each i∈37,38,…,r−40, ∪j=ii+3Xj2≥6 (respectively, ∪j=ii+3Yj2≥6).Proof.
We show that the result holds for∪j=ii+3Xj2 as it follows analogously on ∪j=ii+3Yj2. Clearly, xi+1∈Xi+10⊆Xi+12, xi+2∈Xi+20⊆Xi+22 and xi+1xi+2∈EG. Also, degxi+1,degxi+2≥δG≥κG=3. Furthermore, Nxi+1∪Nxi+2⊆∪j=ii+3Xj1, and each pair of vertices (in this case xi+1 and xi+2) shares at most one neighbour since G is C4-free. There are two cases to consider:Case 1: suppose thatxi+1 and xi+2 do not share a neighbour. Then, ∪j=ii+3Xj2≥∪j=ii+3Xj1≥Nxi+1⊎Nxi+2≥3+3=6, and we are done.Case 2: assume thatxi+1 and xi+2 share a neighbour, say a. Note that a∉Xi2∪Xi+32 since Xi2∩Nxi+2∪Xi+32∩Nxi+1=∅. From this, it becomes obvious that a∉xi,xi+3. Thus, since a is adjacent to xi+1 and xi+2, we realise that a∈Xi+11∪Xi+21. Now, a,xi,xi+1,xi+2,xi+3⊆∪j=ii+3Xj1⊆∪j=ii+3Xj2. Observe that since dega≥δG≥κG=3, a has at least one neighbour b∉xi+1,xi+2. Again since axi+1,axi+2,xixi+1,xi+1xi+2,xi+2xi+3⊆EG and because G is C4-free, we see that b∉xi,xi+3. Because ab∈EG and a∈Xi+11∪Xi+21, we see that b∈∪j=ii+3Xj2. Therefore, ∪j=ii+3Xj2≥b⊎a,xi,xi+1,xi+2,xi+3=6, which settles Lemma 2.
Fori∈37,38,…,r−40, let S be an induced subgraph of G such that VS=∪j=ii+3Xj9 (respectively, VS=∪j=ii+3Yj9) and H be an induced subgraph of S. Then, we have the following definitions.Definition 1.
S is a scant subgraph of G (or simply, S is scant) if VS≤8.Definition 2.
We sayH is an attached subgraph of S (or simply, H is attached) if there exists a path in H connecting at least one vertex u∈Xi9 (respectively, u∈Yi9) to at least one vertex v∈Xi+39 (respectively, v∈Yi+39), otherwise H is a detached subgraph of S (or simply, H is detached).Definition 3.
S is said to be a detachable subgraph of G (or simply, S is detachable) if there exists a vertex v∈VS such that H=S−v is a detached subgraph of S.Lemma 3.
IfS is scant, then it is detachable.Proof.
We show that the result holds forS=∪j=ii+3Xj9 as it follows analogously on S=∪j=ii+3Yj9. Note that if H=S−Xj9, j∈i,i+1,i+2,i+3, then H is detached. Thus, if 1∈Xj9:j∈i,i+1,i+2,i+3, we immediately conclude that S is detachable. So, suppose that Xj9≥2 whenever j∈i,i+1,i+2,i+3. Now, because of our supposition, if Xj9≥3 for any j∈i,i+1,i+2,i+3, then ∪j=ii+3Xj9≥9 contradicting the condition of this lemma. Thus, Xj9<3 whenever j∈i,i+1,i+2,i+3, and consequently, Xi9=Xi+19=Xi+29=Xi+39=2. Accordingly, Xi9+Xi+19+Xi+29=6 and Xi+19+Xi+29+Xi+39=6. For j∈i,i+1,i+2,i+3, let aj be the other vertex in Xj9 which is not xj. Note that a path P=aiai+1ai+2ai+3 such that ai,ai+1,ai+2,ai+3⊆∪j=ii+3Xj8,9 does not exist since G−xi,xi+3 would be disconnected, thereby contradicting κ=3. If ai+1∈Xi+19 or ai+2∈Xi+29, then S is detachable since H=S−xi+1 or H=S−xi+2 is detached. So, suppose ai+1∈Xi+18 and ai+2∈Xi+28. If ai+1xi+1∉EG, then since ai+1 and xi+1 can share at most one neighbour and δ≥3, ∪j=ii+2Xj9≥Nai+1∪Nxi+1≥7 immediately contradicting Xi9+Xi+19+Xi+29=6. Thus, ai+1xi+1∈EG. From a similar argument, we obtain ai+2xi+2∈EG. Note that ai+2 is necessarily adjacent to at least one vertex in Xi+19. Observe that ai+1ai+2∉EG, otherwise ai+1ai+2,ai+2xi+2,xi+2xi+1,xi+1ai+1 would form a C4-subgraph, which is illegal. Thus, ai+2 can only be adjacent to xi+1∈Xi+19. Consider xi+2. Note that ai+1xi+2∉EG, otherwise ai+1xi+2,xi+2ai+2,ai+2xi+1,xi+1ai+1 would form a C4-subgraph, which is forbidden. From the above, we see that H=S−xi+1 is detached, and thus, S is detachable and Lemma 3 is settled.Lemma 4.
IfS is scant, then ∪j=i+1i+3Xj6=∅ (respectively, ∪j=i+1i+3Yj6=∅).Proof.
We show that the result holds forS=∪j=ii+3Xj9 as it follows analogously on S=∪j=ii+3Yj9. Suppose to the contrary that there exists a∈∪j=i+1i+3Xj6. There are two cases to consider:(i)
Case 1: supposea∈Xi+16∪Xi+26. This means a∈Xi+16 or Xi+26. If a∈Xi+16 (a∈Xi+26), then Na∩Nxi+1=∅ (Na∩Nxi+2=∅) yielding ∪j=ii+2Xj9≥Na⊎Nxi+1≥8 (∪j=i+1i+3Xj9≥Na⊎Nxi+2≥8). Thus, since Xi+39≥1 (Xi9≥1), we obtain ∪j=ii+3Xj9≥8+1=9 (∪j=ii+3Xj9≥1+8=9) contradicting our assertion that S is scant.Case 2: supposea∈Xi+36. If this is so, then a is necessarily adjacent to some b∈Ni+2. More specifically, b∈Xi+25,7. Observe that Nb∩Nxi+2=∅. Thus, ∪j=i+1i+3Xj9≥Nb⊎Nxi+2≥8. Taking into account Xi9≥1, we obtain ∪j=ii+3Xj9≥1+8=9 contradicting the condition of the lemma. Thus, Lemma 4 is settled.Lemma 5.
IfS=∪j=ii+3Xj9 (respectively, S=∪j=ii+3Yj9) and S′=∪j=i+4i+7Xj9 (respectively, S′=∪j=i+4i+7Yj9) are both scant, then S=S′=8.Proof.
We show that the result holds forS=∪j=ii+3Xj9, S′=∪j=i+4i+7Xj9 as it follows analogously on S=∪j=ii+3Yj9, S′=∪j=i+4i+7Yj9. By Lemma 4, ∪j=i+1i+3Xj6∪∪j=i+5i+7Xj6=∅.Claim 1.
Xi+46=∅.Proof of Claim1.
Suppose to the contrary that there existsa∈Xi+46. Remember that Q≤da is the set of all vertices in G whose distance from a∈VG is at most d in G. Since δG≥κG=3 and G is C4-free, we have Q≤2a≥8. Note that Q≤2a⊆∪j=i+2i+6Xj4,8. Hence, ∪j=i+2i+3Xj4,8+∪j=i+4i+6Xj4,8≥Q≤2a≥8. There are two cases to consider:Case 1: suppose that∪j=i+4i+6Xj4,8≥3. Note that ∪j=i+4i+6Xj4,8∩∪j=i+4i+7Xj2=∅. Thus, upon making use of Lemma 2, we arrive at ∪j=i+4i+7Xj9≥∪j=i+4i+6Xj4,8⊎∪j=i+4i+7Xj2≥3+6=9 immediately contradicting the condition that S′ is scant.Case 2: now, suppose that∪j=i+4i+6Xj4,8<3. Then, ∪j=i+2i+3Xj4,8≥6, and since ∪j=i+2i+3Xj4,8∩∪j=ii+3Xj2=∅, we obtain, as a consequence of Lemma 2, ∪j=ii+3Xj9≥∪j=i+2i+3Xj4,8⊎∪j=ii+3Xj2≥6+6=12 which contradicts the condition that S is scant. Thus, Xi+46=∅ and our claim is settled.
By Lemma3, S and S′ are both detachable. In other words, there exist u,v∈VG such that H=S−u and H′=S′−v are both detached.Claim 2.
u=xi+3 and v=xi+4Proof of Claim2.
Suppose to the contrary thatu≠xi+3 or v≠xi+4. Observe that since H=S−u (H′=S′−v) is a detached subgraph of S (S′), every path connecting some vertex in Xi9 (Xi+49) to some vertex in Xi+39 (Xi+79) contains u (v). This means that every path connecting some vertex in Xi9 to some vertex in Xi+79 contains u and v. Thus, if u≠xi+3 (v≠xi+4), since H and H′ are detached subgraphs of S and S′, respectively, and also noting that ∪j=i+1i+7Xj6=∅, we see that there is no path connecting xi+3 (xi+4) to z in G−u,v contradicting κG=3. Hence, u=xi+3 and v=xi+4, settling our claim.
We now considerS=∪j=ii+3Xj9. If Xj9=1 for j∈i,i+1,i+2, then H=S−xj is detached, contradicting Claim 2. Thus, Xj9≥2 for j∈i,i+1,i+2. If Xi+39≥3, we obtain ∪j=ii+3Xj9≥2+2+2+3=9 contradicting the condition of the lemma. Thus, Xi+39≤2. If Xi+39=2, we are done since ∪j=ii+3Xj9≥2+2+2+2=8, so suppose Xi+39=1. This means that ∪j=ii+3Xj9≥7, and thus, it remains to prove the following claim.Claim 3.
∪j=ii+3Xj9≠7Proof of Claim3.
Suppose to the contrary thatXj=ii+3=7. This means that Xi9=Xi+19=Xi+29=2 and Xi+39=1. This yields ∪j=ii+2Xj9=6 and ∪j=i+1i+3Xj9=5. Let aj, j∈i,i+1,i+2 be the vertex in Xj9 which is not xj. If aj∈Xj9, then H=S−xj is detached contradicting Claim 2. Thus, aj∈Xj8. Now if ai+1xi+1∉EG, then since ai+1 and xi+1 can share at most one neighbour, we have ∪j=ii+2Xj9≥Nai+1∪Nxi+1≥7, contradicting ∪j=ii+2Xj9=6. A similar argument leads us to conclude that ai+2xi+2∈EG. Observe that ai+2 is necessarily adjacent to at least a vertex in Xi+19. Note that if ai+1ai+2∈EG, then ai+1ai+2,ai+2xi+2,xi+2xi+1,xi+1ai+1 forms a C4-subgraph which is illegal. Thus, ai+2 can only be adjacent to xi+1∈Xi+19 leading us to conclude that ai+2xi+1∈EG. Now, consider xi+2. If xi+2ai+1∈EG, then xi+2ai+1,ai+1xi+1,xi+1ai+2,ai+2xi+2 would form C4-subgraph which is illegal. Thus, xi+2ai+1∉EG. Hence, H=S−xi+1 is detached, contradicting Claim 2. Hence, Claim 3 is settled.
Thus, since∪j=ii+3Xj9≥7 and ∪j=ii+3Xj9≠7, we have ∪j=ii+3Xj9≥8. Therefore, since S is scant, we conclude ∪j=ii+3Xj9=8. A similar set of arguments leads us to conclude that S′=∪j=i+4i+7Xj9=8, thereby settling Lemma 5.Lemma 6.
(a)
IfS=∪j=ii+3Xj9 and S′=∪j=i+4i+7Xj9 are both scant, then S″=∪j=i+8i+11Xj9 is not scant.(b)
IfS=∪j=ii+3Yj9 and S′=∪j=i+4i+7Yj9 are both scant, then S″=∪j=i+8i+11Yj9 is not scant.Proof.
We show that the result holds for (a) as it follows analogously for (b). Suppose to the contrary thatS, S′, and S″ are all scant. By Lemma 4, ∪j=i+1i+3Xj6∪∪j=i+5i+7Xj6∪∪j=i+9i+11Xj6=∅. By Claim 1, Xi+46∪Xi+86=∅; therefore, ∪j=i+1i+11Xj6=∅. Since S, S′, and S″ are all scant, we know, by Lemma 3, that S, S′, and S′′ are all detachable. Observe that, by Claim 2, H=S−xi+3 and H″=S″−xi+8 are both detached. Thus, since ∪j=i+1i+11Xj6=∅, we have it that there is no path connecting xi+4,xi+5,xi+6,xi+7 to z in G−xi+3,xi+8. Thus, G−xi+3,xi+8 is disconnected, contradicting κG=3. This settles Lemma 6.
Throughout the remainder of this paper, we assume thatr−3≡cmod4, c∈0,1,2,3, and we define the set I=10,11,…,r−40−c/4.Lemma 7.
Letl,p,q∈I such that p+1<q.(a)
IfSp=∪j=4p4p+3Xj9 and Sq=∪j=4q4q+3Xj9 are both scant and Sl=∪j=4l4l+3Xj9 is not scant whenever p<l<q, then there exists d (where p+1≤d≤q−1) such that ∪j=4d4d+3Xj9≥12 or ∪j=4d−44d+3Xj9≥21 or ∪j=4d4d+7Xj9≥21.(b)
IfSp=∪j=4p4p+3Yj9 and Sq=∪j=4q4q+3Yj9 are both scant and Sl=∪j=4l4l+3Yj9 is not scant whenever p<l<q, then there exists d (where p+1≤d≤q−1) such that ∪j=4d4d+3Yj9≥12 or ∪j=4d−44d+3Yj9≥21 or ∪j=4d4d+7Yj9≥21.Proof.
We show that the result holds for (a) as it follows analogously for (b). From Lemma4, we have ∪j=4p+14p+3Xj6∪∪j=4q+14q+3Xj6=∅. Suppose there exists a vertex a∈X4q6. Remember that Q≤2a≥8. Consider Q≤3a. If Q≤3a≤8, then Q≤3a−Q≤2a=∅ and there would be no path from a to z contradicting the condition that G is connected. Thus, Q≤3a≥9. Since a∈X4q6, we have Q≤3a⊆∪j=4q−34q+3Xj3,9 and consequently ∪j=4q−34q+3Xj3,9≥Q≤3a≥9. Note that ∪j=4q4q+3Xj3,9∩∪j=4q4q+3Xj2=∅; furthermore, Sq=∪j=4q4q+3Xj9 is scant. Thus, making use of Lemma 2, we obtain ∪j=4q4q+3Xj3,9≤2. This gives us ∪j=4q−34q−1Xj3,9≥7, and using Lemma 2 again, we obtain ∪j=4q−34q−1Xj9≥∪j=4q−44q−1Xj3,9⊎∪j=4q−44q−1Xj2≥7+6=13 and we are done. So, for the rest of this lemma, we will assume X4q6=∅.Claim 4.
There exists a vertexa∈∪j=4p+44q−1Xj6.Proof of Claim4.
Suppose to the contrary that∪j=4p+44q−1Xj6=∅, then ∪j=4p+14q+3Xj6=∅. Since Sp and Sq are both scant, we have it, by Lemma 2, that Sp and Sq are both detachable. Thus, there exist u and v such that Hp=Sp−u and Hq=Sq−v are both detached. Thus, there is no path in G−u,v connecting x4p+4,x4p+5,…,x4q−1 to z. Thus, G−u,v is disconnected, contradicting κG=3 and therefore Claim 4 is settled.
Now we have it, by Claim4, that there exists d∈p+1,p+2,…,q−1 such that a∈∪j=4d4d+3Xj6. With this in mind, there are four cases to consider.Case 1: supposea∈X4d6. Since Q≤3a⊆∪j=4d−34d+3Xj3,9 and ∪j=4d−34d+3Xj3,9∩∪j=4d−44d+3Xj2=∅, we have, by Lemma 2 and Q≤3a≥9, that(8)∪j=4d−44d+3Xj9≥∪j=4d−34d+3Xj3,9+∪j=4d−44d+3Xj2≥Q≤3a+∪j=4d−44d−1Xj2+∪j=4d4d+3Xj2≥9+6+6=21.Case 2:a∈X4d+16. It is obvious that Tz,a∩N4d−2 is nonempty; hence, there exists a vertex b∈Tz,a∩N4d−2. Observe that dGa,b=dGz,a−dGz,b=4d+1−4d−2=3. Thus, since a∈X4d+16, we have b∈X4d−23,9 and thus X4d−23,9≥1. Furthermore, Q≤2a⊆∪j=4d−14d+3Xj4,8 and ∪j=4d−14d+3Xj4,8∩∪j=4d−44d+3Xj2=∅. Hence, by Lemma 2,(9)∪j=4d−44d+3Xj9≥X4d−23,9+∪j=4d−14d+3Xj4,8+∪j=4d−44d−1Xj2+∪j=4d4d+3Xj2≥1+8+6+6=21.Case 3:a∈X4d+26. Note that a is necessarily adjacent to at least one vertex, say b, in X4d+19. More specifically, b∈X4d+15,7. Observe that Na∪Nb⊆∪j=4d4d+3Xj4,8 and ∪j=4d4d+3Xj4,8∩∪j=4d4d+3Xj2=∅. Thus, if a and b do not share any neighbours, we are done, by Lemma 2, since ∪j=4d4d+3Xj9≥∪j=4d4d+3Xj4,8+∪j=4d4d+3Xj2≥Na∪Nb+∪j=4d4d+3Xj2≥6+6=12. So, suppose a and b share a neighbour, say c. Note that c∉X4d9∪X4d+39 since X4d9∩Na∪X4d+39∩Nb=∅. Thus, a,b,c⊆X4d+14,8∪X4d+24,8. Since G is C4-free, any pair of vertices can only share at most one neighbour. Recognise that a and b share c, also b and c share a, and finally a and c share b. Furthermore, dega,degb,degc≥3;thus, a is adjacent to another vertex, say a′, b is adjacent to another vertex, say b′, and c is adjacent to another vertex, say c′, such that a′≠b′≠c′≠a′. Thus, since a,a′,b,b′,c,c′⊆Na∪Nb∪Nc⊆∪j=4d4d+3Xj3,9 and ∪j=4d4d+3Xj3,9∩∪j=4d4d+3Xj2=∅, we obtain, by Lemma 2, ∪j=4d4d+3Xj9≥∪j=4d4d+3Xj2+∪j=4d4d+3Xj3,9≥6+6=12.(i)
Case 4:a∈X4d+36. Since Q≤3a⊆∪j=4d4d+6Xj3,9 and ∪j=4d4d+6Xj3,9∩∪j=4d4d+7Xj2, we have, by Lemma 2 and Q≤3a≥9, that(10)∪j=4d4d+7Xj9≥∪j=4d4d+7Xj3,9+∪j=4d4d+7Xj2≥Q≤3a+∪j=4d4d+3Xj2+∪j=4d+44d++7Xj2≥9+6+6=21.
Thus, Lemma7 is settled.
Throughout the remainder of this paper, forp∈I, we define Sp=∪j=4p4p+3Xj9 (respectively, Sp′=∪j=4p4p+3Yj9) and sp=Sp (respectively, sp′=Sp′).Lemma 8.
Letp,q∈I.(a)
IfSp and Sq are both scant and Sl is not scant whenever l∈p+2,p+3,…,q−1, then ∑j=pq−1sp≥9q−p.(b)
IfSp′ and Sq′ are both scant and Sl′ is not scant whenever l∈p+2,p+3,…,q−1, then ∑j=pq−1sp′≥9q−p.Proof.
We show that the result holds for (a) as it follows analogously for (b). By Lemma7, there exists d∈p+1,p+2,…,q−1 such that sd≥12 or sd−1+sd≥21 or sd+sd+1≥21. Note that sp+sp+1≥15 since if Sp+1 is scant, we obtain, by Lemma 5, sp+sp+1=8+8=16>15, otherwise we have, by Lemma 2, sp+sp+1≥6+9=15.(i)
Case 1:d∈p+3,p+4,…,q−2. Since sp+sp+1≥15 and sl≥9 whenever l∈p+2,p+3,…,q−1, we have the following. If sd≥12, then(11)∑j=pq−1sj≥sp+sp+1+∑j=p+2d−1sj+sd+∑j=d+1q−1sj≥15+9d−1−p+1+12+9q−1−d=9q−p.Ifsd−1+sd≥21, then(12)∑j=pq−1sj≥sp+sp+1+∑j=p+2d−2sj+sd−1sd+∑j=d+1q−1sj≥15+9d−2−p+1+21+9q−1−d=9q−p.(i)
Ifsd+sd+1≥21, then(13)∑j=pq−1sj≥sp+sp+1+∑j=p+2d−1sj+sd+sd+1+∑j=d+2q−1sj≥15+9d−1−p+1+21+9q−1−d+1=9q−p.Case 2:d=p+1. It is obvious in this case that Sp+1 is not scant, thus making use of the condition of the current lemma, and sl≥9 whenever l∈p+1,p+3,…,q−1. Note that, by Lemma 2, sp≥6. If sd≥12, then(14)∑j=pq−1sj=sp+sp+1=d+∑j=p+2q−1sj≥6+12+9q−1−p+1=9q−p.Ifsd−1+sd≥21, then(15)∑j=pq−1sj=sp=d−1+sp+1=d+∑j=p+2q−1sj≥21+9q−1−p+1=9q−p+3.Ifsd+sd+1≥21, then(16)∑j=pq−1sj=sp+sp+1=d+sp+2=d+1+∑j=p+3q−1sj≥6+21+9q−1−p+2=9q−p.Case 3:d=p+2. If sd≥12, then(17)∑j=pq−1sj=sp+sp+1+sp+2=d+∑j=p+3q−1sj≥15+12+9q−1−p+2=9q−p.Ifsd−1+sd≥21, then(18)∑j=pq−1sj=sp+sp+1=d−1+sp+2=d+∑j=p+3q−1sj≥6+21+9q−1−p+2=9q−p.Ifsd+sd+1≥12, then(19)∑j=pq−1sj=sp+sp+1+sp+2=d+sp+3=d+1+∑j=p+4q−1sj≥15+21+9q−1−p+3=9q−p.Case 4:d=q−1. If sd≥12, then(20)∑j=pq−1sj=sp+sp+1=d+∑j=p+2q−2sj+sq−1≥15+9q−2−p+1+12=9q−p.Ifsd−1+sd≥21, then(21)∑j=pq−1sj=sp+sp+1+∑j=p+2q−3sj+sq−2=d−1+sq−1=d≥15+9q−3−p+1+21=9q−p.
Ifsd+sd+1≥21, we have the following. Since Sq is scant, we have sq≤8 and, therefore, sq−1≥13. Then,(22)∑j=pq−1sj=sp+sp+1+∑j=p+2q−2sj+sq−1≥15+9q−2−p+1+13=9q−p+1.
Thus, Lemma8 is settled.Lemma 9.
(a)
∑j∈Isj≥9I−3.(b)
∑j∈Isj′≥9I−3.Proof.
We show that the result holds for (a) as it follows analogously for (b). IfSj is not scant for all j∈I, then sj≥9 for all j∈I and ∑j∈Isj≥9I. If there exists only one p∈I such that Sp is scant, then ∑j∈Isj=∑j∈I−psj+sp≥9I−1+6=9I−3. If there exist at least two p∈I such that Sp is scant, then we have the following. Let p1,p2,…,pm∈Θ1 such that Spj is scant whenever j∈1,2,…,m. Define Θ2=pj∈Θ1:pj−1=pj−1 and Θ3=Θ1−Θ2. We denote the elements of Θ3 as q1,q2,…,qf, where q1<q2<⋯<qf. Let I′=q1,q1+1,q1+2,…,qf−1,qf. Thus, applying Lemma 2 and Lemma 8, we obtain(23)∑j∈Isj=∑j∈I−I′sj+∑j∈I′−qfsj+sqf≥9I−I′+∑i=1f−1∑j=qiqi+1−1sj+6≥9I−qf−q1−1+∑i=1f−19qi+1−qi+6≥9I−9qf−q1−3+9qf−q1=9I−3.Theorem 2.
LetG be a 3-vertex-connected C4-free graph of order n. Then, radG≤2n/9+263/9.Proof.
Remember thatki=|Ni, 0≤i≤r. Note that, since G is 3-vertex-connected, ki≥3, 0<i<r. Note also that, since N0,Nr≠∅, k0,kr≥1, 0<i<r. Thus, by 1 and Lemma 9, we obtain(24)n=∪j=0rNj=1+∪j=139Nj+∪j=40r−37−cNj+∪r−36−crNj≥∪j=039Nj+∪j=40r−37−cXj9+∪j=40r−37−cYj9+∪r−36−cr−1Nj+1≥2+∑j=139kj+∑j∈Isj+∑j∈Isj′+∑r−36−crkj≥3⋅40+9I−3+9I−3+3⋅36+c=18I+221+c=18r−40−c4−9+221+c=9r2−121−7c2≥9r2−121−212=9r2−2632.
Thus,radG≤2n/9+263/9 as desired.
To show that this bound is asymptotically sharp, consider the graph described immediately following Theorem1.



---

*Source: 8367408-2020-08-04.xml*