# Retractions and Homomorphisms on Some Operations of Graphs

Authors: M. Abu-Saleem
Journal: Journal of Mathematics
 (2018)

---

## Abstract

The aim of the present article is to introduce and study a new type of operations on graph, namely, edge graph. The relation between the homomorphisms and retractions on edge graphs is deduced. The limit retractions on the edge graphs are presented. Retractions on a finite number of edge graphs are obtained.


---

## Body

## 1. Introduction and Preliminaries

Graph theory is rapidly moving into the mainstream of mathematics. The prospects of further development in algebraic graph theory and important link with computational theory indicate the possibility of the subject quickly emerging at the forefront of mathematics. Its scientific and engineering applications, especially to communication science, computer technology, and system theory, have already been accorded a place of pride in applied mathematics. Graphs serve as mathematical models to analyze successfully many concrete real-world problems. A certain problem in physics, chemistry, genetics, psychology, sociology, and linguistics can be formulated as problems in graph theory. Also, many branches of mathematics such as game theory, group theory, matrix theory, probability, and topology have interactions with graph theory. Some puzzles and various problems of a practical nature have been instrumental in the development of various topics in graph theory. The theory of acyclic graphs was developed for solving problems of electrical networks and the study of trees was developed for enumerating isomers of organic compounds. This paper describes the operation of a graph from the viewpoint of an identification [1–10].A graph is an orderedG=(V(G),E(G)), where V(G)≠ϕ, E(G) is a set disjoint from V(G), elements of V(G) are called the vertices of G, and elements of E(G) are called the edges. A graph is connected if, for every partition of its vertex set into two nonempty sets X and Y, there is an edge with one end in X and one end in Y; otherwise, the graph is disconnected. A graph H is said to be a subgraph of a graph G if V(H)⊆V(G) and E(H)⊆E(G). A graph in which each pair of distinct vertices is adjacent is called a complete graph. A complete graph with n vertices is denoted by Kn [11]. The chromatic number χ(G) of a graph G is the minimum number of colors required for proper vertex coloring of G. A m-coloring of a graph G is a vertex coloring of G that uses at most m-colors. A graph G is said to be m-colorable if G admits a proper vertex coloring using at most m colors [11]. Let G and H be two graphs. A function ϕ:V(G)→V(H) is a homomorphism from G to H if it preserves edges, that is, if for any edge [u,v] of G, [ϕ(u),ϕ(v)] is an edge of H [12]. A retract of a graph G is a subgraph H of G such that there exists a homomorphism r:G→H, called retraction with r(x)=x for any vertex x of H [7]. A core is a graph which does not retract to a proper subgraph [12].


## 2. The Main Results

Aiming at our study, we will introduce the following.Definition 1.
LetG1 and G2 be two connected graphs, where e1 is an edge of G1, e2 is an edge of G2, and G1∩G2=ϕ; then we define the edge graph G1∨_G2 by gluing together the two edges e1 and e2.Theorem 2.
LetG1 and G2 be two connected graphs. Then χ(G1∨_G2)=max⁡{χ(G1),χ(G2)}.Proof.
Letχ(G1∨_G2)=m. At that point, there exists an m-coloring ϖ of G1∨_G2. Since ϖ assigns different colors to every two adjacent vertices of G1 and G2, G1 and G2 are m-colorable and so χ(G1)≤χ(G1∨_G2) and χG2≤χG1∨_G2. Also, using symmetry χ(G1)≥χ(G2). Beginning with an ideal coloring of χ(G1), we can incorporate an ideal coloring of χ(G2) by exchanging a pair of color names to make the coloring agree at two vertices of common edge graphs. This produces a proper coloring of G1∨_G2.Theorem 3.
The graphsG1 and G2 are subgraphs of G1∨_G2. Also, for any tree G1 and G2, the graph G1∨_G2 is also a tree.Proof.
The proof of this theorem is clear.Theorem 4.
Suppose thatG1,G2,…,Gn are connected graphs; then there is a sequence of nontrivial retractions {rk:∨_i=1nGi→∨_i=1nGi,k=1,2.…n}, where ∨_i=1nGi are glued along the same edge such that rk(∨_i=1nGi) is a proper subgraph of ∨_i=1nGi.Proof.
Letr1:∨_i=1nGi→∨_i=1nGi be a retraction from ∨_i=1nGi into itself and r1(∨_i=1nGi)=G1∨_G2∨_…∨_r1(Gs)…∨_Gn for s=1,2,…,n. Since r1(Gs) is a proper subgraph of Gs, it follows that r1(∨_i=1nGi) is a proper subgraph of ∨_i=1nGi. Also, if r2(∨_i=1nGi)=G1∨_G2∨_⋯∨_r2(Gs)∨_⋯∨_r2(Gk)∨_⋯∨_Gn for k=1,2,…,n,s<k and r2(Gs),r2(Gk) are subgraphs of Gs,Gk, respectively, then r2(∨_i=1nGi) is a proper subgraph of ∨_i=1nGi. Moreover, by continuing this process if rn(∨_i=1nGi)=∨_i=1nrn(Gi), then rk(∨_i=1nGi) is a proper subgraph of ∨_i=1nGi.Theorem 5.
LetG1 and G2 be two graphs; then there is a homomorphism f:G1→G2 iff G2 is a retract of G1∨_G2.Proof.
Letf:G1→G2 be a homomorphism. Since G2 is subgraph of G1∨_G2, then there exists a homomorphism r:G1∨_G2→G2with r(x)=x, for any vertex x of G2 and so G2 is a retract of G1∨_G2. Conversely, assume that G2 is a retract of G1∨_G2; thus r:G1∨_G2→G2 is a homomorphism with r(x)=x for any vertex x of G2, and so there is a homomorphism f:G1→G2.Theorem 6.
LetG1 and G2 be connected graphs; then Kn is a retract of graph G1 or G2, iff Kn retract of G1∨_G2.Proof.
SupposeG1 and G2 are connected graphs and Kn is a retract of graph G1 or G2. Then there is a homomorphism r1:G1→Kn such that r1(x)=x, or a homomorphism r2:G2→Kn such that r2(x)=x, for any vertex x of Kn. Since Kn is a core and it is subgraph of G1 or G2, it follows that Kn is subgraph of G1∨_G2 and so there is a homomorphism r:G1∨_G2→Kn such that r(x)=x, for any vertex x of Kn. Conversely, suppose Kn is a retract G1∨_G2; then Kn is subgraph of G1∨_G2 and Kn∨_Kn and so Kn is a retract of graphs G1 or G2.Theorem 7.
LetT be any tree of size n; then there is a sequence of nontrivial retractions ri,i=1,2,…n such that limn→∞rn(rn-1)…(r1(T)=K2.Proof.
Consider the following sequence of retractions:
r 1 : T → T 1 is nontrivial retraction, where T1 is subgraph of T and 1≤SizeT1≤n-1,
r 2 : r 1 T → r 1 T 1, where r1T1 is subgraph of r1T and 1≤Sizer1T1≤n-2,
⋮
r n : r n - 1 ( r n - 2 ) … ( r 1 ( T ) → r n - 1 ( r n - 2 ) … ( r 1 ( T 1 ), where rn-1(rn-2)…(r1(T1) is subgraph of rn-1(rn-2)…(r1(T), and limn→∞rn(rn-1)…(r1(T) is a tree of size 1. Therefore, limn→∞rn(rn-1)…(r1(T)=k2.Theorem 8.
Suppose thatG1 and G2 are connected graphs; then limn→∞rn(G1∨_G2))=limn→∞rn(G1)∨_limn→∞rn(G1).Proof.
IfG1 and G2 are connected graphs, then we get the following induced subgraphs limn→∞rn(G1∨_G2)),limn→∞rn(G1),limn→∞rn(G1) and each of them is isomorphic to k2. Since, k2≈k2∨_k2, it follows that limn→∞rn(G1∨_G2))=limn→∞rn(G1)∨_limn→∞rn(G1).


## 3. Some Applications in Chemistry and Biology

(i) A polymer is composed of many repeating units called monomers. Starch, cellulose, and proteins are natural polymers. Nylon and polyethylene are synthetic polymers. Polymerization is the process of joining monomers. Polymers may be formed by addition polymerization and one basic step in addition polymerization is combination as in Figure1, which occurs when the polymer’s growth is stopped by free electrons from two growing chains that join and form a single chain. The following diagram depicts combination, with the symbol (R) representing the rest of the chain. This is a representation type of connected two graphs into an edge graph.Figure 1(ii) Peptide bonds constitute the representation of an edge graph by linking two amino acids as in Figure2, which is a representation graph of connected two typical amino acids into an edge graph.Figure 2In Figure3, peptide pond and formation hydrolysis: Formation (top to bottom) and hydrolysis from bottom to top of a peptide bonds require conceptually loss and addition, respectively, of a molecule of water. The actual chemical synthesis and hydrolysis of peptide bonds in the cell are enzymatically controlled processes that in the synthesis nearly always occur on the ribosome and are directed by an mRNA template. The end of a polypeptide with the free of amino group is known as the amino terminus (N terminus) and with the free carboxyl group is the carboxyl terminus (C terminus). This is a representation of connected two graphs into an edge graph.Figure 3



---

*Source: 7328065-2018-10-01.xml*