# Fixed Points ofG-Type Quasi-Contractions on Graphs

Authors: R. H. Haghi; Sh. Rezapour; N. Shahzad
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Recently, fixed point theory on graphs has been considered by many authors. In this paper, by combining some ideas in some published papers and introducingG-type quasi-contractions, we give some fixed point results for G-type quasi-contractions on graphs. The results improve some old results in the literature.


---

## Body

## 1. Introduction

In 2009, Ilić and Rakočević proved that quasi-contraction maps on normal cone metric spaces have a unique fixed point [1]. Then, Kadelburg et al. generalized their results by considering an additional assumption [2]. Also, they proved that quasi-contraction maps on cone metric spaces have the property (P) whenever λ∈(0,1/2). Later, the authors proved same results without the additional assumption and for λ∈(0,1) by providing a new technical proof [3]. Also, there are some works on quasi-contractive multifunctions (see, e.g., [4, 5]).In 2008, Suzuki introduced a new type of mappings and a generalization of the Banach contraction principle [6]. Later, his method extended for mappings and multifunctions (see, e.g., [7] and the references therein and [8]). On the other hand, Echenique gave a short constructive proof for Tarski's fixed point theorem in 2005 by using graphs [9]. In 2006, Espínola and Kirk started combining fixed point theory and graph theory [10]. In 2008, Jachymski provided some fixed point results for Banach contractions on a graph [11]. Recently, fixed point theory on graphs has been considered by many authors (see, e.g., [12–16]).Let(X,d) be a metric space, Δ={(x,x):x∈X}, G a directed graph G such that V(G)=X, and the set E(G) of its edges contains all loops. We denote the conversion of a graph G by G-1; that is, the graph obtained from G by reversing the direction of the edges. Moreover, G~ denotes the undirected graph obtained from G by ignoring the direction of the edges. In this paper, we consider undirected graphs. We say that a self-map T on X preserves the edges of G whenever (x,y)∈E(G) which implies that (Tx,Ty)∈E for all x,y∈X. A finite path of length n in G from x to y is a sequence {xi}i=0n of distinct vertices such that x0=x, xn=y, and (xi,xi+1)∈E(G) for i=0,1,…,n-1 (see, e.g., [12]). A graph G is connected if there is a path between any two vertices. G is weakly connected if G~ is connected. We denote by [x]G the set of all vertices in G that there is a path between x and those.In 2008, Jachymski used the notion ofC-graphs for obtaining the main results of [11]. We say that G is a C-graph whenever for each sequence {xn}n≥0 in X with xn→x and (xn,xn+1)∈E(G) for all n≥0, there is a subsequence {xnk}k≥0 such that (xnk,x)∈E(G) for all k≥0 [11]. This notion has been used by many authors in the literature, specially on ordered metric spaces and obtaining solutions of some differential equations (see, e.g., [17]).The condition that the graph is aC-graph looks quite strong and in this reason, Aleomraninejad et al. defined the notion of P-graphs and showed that these notions are independent on infinite graphs (see [12]). We say that G is a P-graph whenever {xn}n≥0 is a convergent sequence to a point x and xn∈[x]G for all n≥0, we have r(xn,x)→0 [12]. Here, r(x,y) is the sum of edges distance between x and y; that is, r(x,y)=∑i=1nd(xi-1,xi). They proved the same results for C-graphs and P-graphs (see the results of [12]). We will use only C-graphs in this paper.In this paper, by combining all of these ideas and introducingG-type quasi-contractions, we give some results about fixed points of G-type quasi-contractions on graphs. The results improve some old results in the literature.


## 2. Main Results

Now, we are ready to state and prove our main results. In 2008, Suzuki obtained the following interesting fixed point result [6].Theorem 1.
Let(X,d) be a complete metric space and let T be a self-map on X. Define the nonincreasing function θ from [0,1) onto (1/2,1] by
(1)θ(r)={1if0≤r≤(5-1)2,(1-r)r-2if(5-1)2<r<2-1/2,(1+r)-1if2-1/2≤r<1.
Assume that there exists r∈[0,1), such that
(2)θ(r)d(x,Tx)≤d(x,y)impliesthatd(Tx,Ty)≤rd(x,y)
for all x,y∈X. Then, there exists a unique fixed point z of T. Moreover, limn→∞Tnx=z for all x∈X.Throughout this paper, suppose thatE=E(G) and G is a C-graph.Definition 2.
Let(X,d) be a metric space, T a self map on X, and G a graph with V(G)=X. We say that T is a G-type quasi-contraction whenever T preserves the edges of G and there exists r∈[0,1), such that
(3)θ(r)d(x,Tx)≤d(x,y)impliesthatd(Tx,Ty)≤rM(x,y)
for all (x,y)∈E, where
(4)M(x,y)=max{12[d(x,Ty)+d(y,Tx)]d(x,y),d(x,Tx),d(y,Ty),12[d(x,Ty)+d(y,Tx)]}.Theorem 3.
Let(X,d) be a complete metric space, T a G-type quasi-contraction map with r2+r<1 such that (x,Tx), (x,T2x)∈E(G) for all x∈X. Then, T has a unique fixed point.Proof.
Takex0∈X. Since θ(r)d(x0,Tx0)≤d(x0,Tx0), we have
(5)d(Tx0,T2x0)≤rmax{d(x0,Tx0),d(Tx0,T2x0),12d(x0,T2x0)}≤rmax{d(x0,Tx0),d(Tx0,T2x0)}.
Since (1/2)d(x0,T2x0)≤(1/2)[d(x0,Tx0)+d(Tx0,T2x0)], we obtain d(T2x0,Tx0)≤rd(x0,Tx0). Hence,
(6)d(Tnx0,Tn+1x0)≤rnd(x0,Tx0)
for all natural number n and so {Tnx0}n≥1 is a Cauchy sequence. Since X is complete, {Tnx0}n≥1 converges to some x*∈X. Since G is a C-Graph, there is a subsequence {Tnkx0}k≥1 such that (Tnkx0,x*)∈E for all k≥1. Hence, (Tnk+jx0,Tjx*)∈E for all j≥1. We claim that Tj0x*=x* for some natural number j0. Arguing by contradiction, we assume that Tjx*≠x* for all j. Fix a natural number j and put xn+1=Tnx0 for all n≥1. Choose a natural number n0 such that d(xn,x*)≤d(x*,Tjx*)/3 for all n≥n0. If nk≥n0, then
(7)d(xnk+j,Txnk+j)≤d(xnk+j,x*)+d(x*,xnk+j+1)≤23d(x*,Tjx*)=d(x*,Tjx*)-13d(x*,Tjx*)≤d(x*,Tjx*)-d(xnk+j,x*)≤d(xnk+j,Tjx*).
It follows that
(8)d(Txnk+j,Tj+1x*)≤rmax{12[d(xnk+j,Tj+1x*)+d(Tjx*,xnk+j+1)]d(xnk+j,Tjx*),d(xnk+j,xnk+j+1),d(Tjx*,Tj+1x*),12[d(xnk+j,Tj+1x*)+d(Tjx*,xnk+j+1)]},
and so d(x*,Tj+1x*)≤rmax{d(x*,Tjx*), d(Tjx*,Tj+1x*)}. Since d(Tjx*,Tj+1x*) ≤ rjd(x*,Tx*), we obtain
(9)d(x*,Tj+1x*)≤rjd(x*,Tx*)
for all j. Now, we assume that d(x*,T2x*)<d(T2x*,T3x*); then by (6), we have
(10)d(x*,Tx*)≤d(x*,T2x*)+d(Tx*,T2x*)<d(T2x*,T3x*)+d(Tx*,T2x*)≤r2d(x*,Tx*)+rd(x*,Tx*).
This is a contradiction, since r2+r<1. So, we have
(11)d(x*,T2x*)≥d(T2x*,T3x*)=θ(r)d(T2x*,T3x*),
and by (3), we obtain
(12)d(T3x*,Tx*)≤rmax{12[d(T2x*,Tx*)+d(x*,T3x*)]d(x*,T2x*),d(T2x*,T3x*),d(x*,Tx*),12[d(T2x*,Tx*)+d(x*,T3x*)]}.
By considering the above inequality and (9), we deduce that
(13)d(x*,Tx*)≤d(x*,T3x*)+d(Tx*,T3x*)≤r2d(x*,Tx*)+rd(x*,Tx*)≤(r2+r)d(x*,Tx*)<d(x*,Tx*),
that is a contradiction. Therefore, there exists j0∈ℕ such that Tj0x*=x*. Since {Tnx*}n≥1 is a Cauchy sequence, we obtain x*=Tx*. In fact, if x*≠Tx*, from d(Tnj0x*,Tnj0+1x*)=d(x*,Tx*) for all n≥1, it follows that {Tnx*}n≥1 is not a Cauchy sequence. Thus, x* is a fixed point of T. The uniqueness of the fixed point follows easily.Question 1.
Does Theorem3 hold for each r∈[0,1)?Theorem 4.
Let(X,d) be a complete metric space. Then, the following statements are equivalent(i)
Gis weakly connected,(ii)
for eachG-type quasi-contraction map T:XT→XT and x,y∈X, the sequences {Tnx}n≥1 and {Tny}n≥1 are Cauchy equivalent, where XT={x∈X:(x,Tx)∈E},(iii)
for eachG-type quasi-contraction map T:X→X, card(FixT)≤1.Proof.
(
i
)
⇒
(
ii
) Let T:X→X be a G-type quasi-contraction map and x,y∈X. Since y∈[x]G~, there is a path {x0=x,…,xN=y} in G~ from x to y. Since (xi-1,xi)∈E(G~), (Tnxi-1,Tnxi)∈E(G~) for all n and i=1,…,N. Let 1≤i≤N. Put xi-1=a and xi=b. If one of the following inequalities holds
(14)θ(r)d(Tn-1a,Tna)≤d(Tn-1a,Tn-1b)orθ(r)d(Tn-1b,Tnb)≤d(Tn-1b,Tn-1a).
Then, we have
(15)d(Tna,Tnb)≤rmax{12[d(Tn-1a,Tnb)+d(Tn-1b,Tna)]d(Tn-1a,Tn-1b),d(Tn-1a,Tna),d(Tn-1b,Tnb),12[d(Tn-1a,Tnb)+d(Tn-1b,Tna)]}:=run.
If un∈{d(Tn-1a,Tna),d(Tn-1b,Tnb)}, then
(16)d(Tna,Tnb)≤rnmax{12d(a,Ta),d(b,Tb)}.
If un=(1/2)[d(Tn-1a,Tnb)+d(Tn-1b,Tna)], then
(17)d(Tna,Tnb)≤rd(Tn-1a,Tnb)ord(Tna,Tnb)≤rd(Tn-1b,Tna).
Without loss of generality, suppose that d(Tna,Tnb)≤rd(Tn-1a,Tnb). Then,
(18)d(Tna,Tnb)≤rd(Tn-1a,Tnb)≤rd(Tn-1a,Tna)+rd(Tna,Tnb),
and so d(Tna,Tnb)≤(r/(1-r))d(Tn-1a,Tna)≤(rn/(1-r))d(a,Ta). Hence,
(19)d(Tna,Tnb)≤rn1-rmax{12d(a,Ta),d(b,Tb)}.
Now, suppose that both of the inequalities (14) do not hold. If
(20)θ(r)d(Tn-1a,Tna)>d(Tn-1a,Tn-1b),
then
(21)d(Tn-1a,Tn-1b)<θ(r)d(Tn-1a,Tna)≤θ(r)rn-1d(a,Ta),
and so
(22)d(Tna,Tnb)≤d(Tna,Tn-1a)+d(Tn-1a,Tn-1b)+d(Tn-1b,Tnb)≤3rn-1max{12d(a,Ta),d(b,Tb)}.
If un=d(Tn-1a,Tn-1b), then we can continue in a similar process for n-1. In the general case, we get d(Tna,Tnb)≤(3rn-1/(1-r))max{d(a,Ta),d(b,Tb)} and so d(Tna,Tnb)→0. Thus,
(23)d(Tnx,Tny)≤∑i=1N‍d(Tnxi-1,Tnxi)≤3rn-11-r≤∑i=1N‍max{12d(xi-1,Txi-1),d(xi,Txi)}≤3N3rn-11-rmax1≤i≤Nd(xi-1,Txi-1).
Therefore, {Tnx}n≥1 and {Tny}n≥1 are Cauchy equivalent.
(
ii
)
⇒
(
iii
) Let x,y∈FixT. By using (ii) and the above process, we obtain easily that x=y.
(
iii
)
⇒
(
i
) If G is not weakly connected, then there exists x0 such that X∖[x0]G~ is not empty. Take y0∈X∖[x0]G~ and define
(24)Tx={x0,x∈[x0]G~,y0,x∈X∖[x0]G~.
Clearly, FixT={x0,y0}. Now, we show that T is a G-type quasi-contraction. For this reason, let (x,y)∈E. Since [x]G~=[y]G~, either x,y∈[x0]G~ or x,y∈X∖[x0]G~. In both cases, we get Tx=Ty. Thus, T is a G-type quasi-contraction which has two fixed points. This contradiction completes the proof.Theorem 5.
Let(X,d) be a complete metric space and let T be a G-type quasi-contraction and orbitally G-continuous self-map on X. Then,(i)
for eachx∈XT, T|[x]G~ is a Picard operator,(ii)
card(FixT)=card{[x]G~:x∈XT}.Proof.
Letx∈XT. Then, Tx∈[x]G~. It is easy to check that {Tn}n≥1 is a Cauchy sequence. Let limn→∞Tnx=x*. Since G is a C-Graph, there exists a subsequence {Tnkx}n≥1 such that (Tnkx,x*)∈E(G) for all k. Thus, (Tnk+1x,Tx*)∈E(G) for all k. Since (Tnkx,Tnk+1x)∈E(G), Tx*∈[x]G~. Since T is orbitally G-continuous, limn→∞Tnk+1x=x* which yields x*=Tx*. To prove (ii), define the mapping π by π(x)=[x]G~ for all x∈FixT. It is sufficient to show that π is a bijection from FixT onto 𝒞={[x]G~:x∈XT}. Since Δ⊆E(G), we get FixT⊆XT which yields π(FixT)⊆𝒞. On the other hand, if x∈XT, then limn→∞Tnx∈[x]G~⋂‍FixT which implies that π(limn→∞Tnx)=[x]G~. Thus, π is a surjection from FixT onto 𝒞. Now, if x1,x2∈FixT with π(x1)=π(x2), then x2∈[x1]G~ and so by using (i) we obtain
(25)limn→∞Tnx2∈[x1]G~⋂‍FixT={x1},
which implies that x2=x1. Therefore, T is an injective and this completes the proof.We need the following results for our last result.Lemma 6 (see [18]).
LetX be a nonempty set and let T:X→X be a mapping. Then, there exists a subset Y⊆X such that TY=TX and T:Y→X is one-to-one.Lemma 7 (see [8]).
LetX be a nonempty set and that the mappings f,T:X→X have a unique point of coincidence v in X. If T and f are weakly compatible, then T and f have a unique common fixed point.Theorem 8.
Let(X,d) be a metric space, and let f and T be two self-maps on X such that TX⊆fX and fX is complete. Suppose that f and T satisfy the following conditions:(i)
(fx,fy)∈E(G) implies that (Tx,Ty)∈E(G),(ii)
if(fx,Tx)∈E(G) and Tx=fy for some y∈X, then (fx,Ty)∈E(G),(iii)
there existsr∈[0,1) such that r2+r<1 and θ(r)d(fx,Tx)≤d(fx,fy) implies that
(26)d(Tx,Ty)≤rmax{12[d(fx,Ty)+d(fy,Tx)]d(fx,fy),d(fx,Tx),d(fy,Ty),12[d(fx,Ty)+d(fy,Tx)]}.Then, T and f have a unique coincidence point. Moreover, if T and f are weakly compatible, then T and f have a unique fixed point.Proof.
By using Lemma6, there exists Y⊂X such that f:Y→X is one-to-one and fY=fX. Define the self-map h:fY→fY by h(fx)=Tx. Clearly, h is well defined and h preserves the edges of G. In fact, (fx,fy)∈E(G) implies that (hfx,hfy)∈E(G). Note that θ(r)d(fx,hfx)≤d(fx,fy) implies that
(27)d(hfx,hfy)≤rmax{12[d(fx,hfy)+d(fy,hfx)]d(fx,fy),d(fx,hfx),d(fy,hfy),12[d(fx,hfy)+d(fy,hfx)]}.
Also, (fx,hfx) and (fx,h2fx) lie in E(G) for all x∈Y. To see this, take hfx=Tx. Then, Tx=fy for some y∈Y and so h2fx=Ty. By using (ii), (fx,Ty)∈E(G). Since fY is complete, by using Theorem 3, h has a unique fixed point in fY, namely, hfx*=fx*. Thus, x* is a coincidence point of f and T. Note that the assumption (iii) shows the uniqueness of the coincidence point of f and T. Now, by using Lemma 7, it is easy to see that if f and T are weakly compatible, then f and T have a unique fixed point.



---

*Source: 167530-2013-11-19.xml*