# Folding List of Graphs Obtained from a Given Graph

Authors: E. M. El-Kholy; H. Ahmed
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

In this paper, we examine the relation between graph folding of a given graph and foldings of new graphs obtained from this graph by some techniques like dual, gear, subdivision, web, crown, simplex, crossed prism, and clique-sum graphs. In each case, we obtained the necessary and sufficient conditions, if exist, for these new graphs to be folded.


---

## Body

## 1. Introduction

LetG=V,E be a graph, where V is the set of its vertices and E is the set of its edges. By a graph, we mean a simple and finite connected graph; that is, a graph without multiple edges or loops. Let G be a graph, then(1)
The dual graphG∗ of a graph G is obtained by placing a vertex in every face of G and an edge joining every two vertices in neighbouring faces [1].(2)
A gear graph, denotedGn, is a graph obtained by inserting an extra vertex between each pair of adjacent vertices on the perimeter of a wheel graph Wn. Thus, Gn has 2n+1 vertices and 3n edges [2].(3)
If the edgee joins vertices v and w, then the subdivision of e replaces e by a new vertex u and two new edges vu and uw [3]. A subdivision of a graph G is a graph obtained from G by applying a finite number of subdivisions of edges in succession.(4)
The web graphWn,r is a graph consisting of r concentric copies of the cycle graphs Cn, with corresponding vertices connected by edges [4].(5)
Crown graph on2n vertices is an undirected graph with two sets of vertices u1,u2,…,un and v1,v2,…,vn and with an edge from uitovj whenever i≠j [5]. The crown graph can be viewed as a complete bipartite graph from which edges ui,vj,i=1,…,n, have been removed.(6)
A simplex graphκG of an undirected graph G is itself a graph, with a vertex for each clique in G. Two vertices of κG are joined by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex. The single vertices are called the zero vertices [6].(7)
A crossed prism graph for positive evenn is a graph obtained by taking two disjoint cycle graphs Cn and adding edges vk,v2k+1 and vk+1,v2k for k=1,3,…,n−1 [7]. We will denote this graph by CPn.(8)
If two graphsG and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, without deleting any of the clique edges [8].(9)
LetG1andG2 be two simple graphs and f:G1⟶G2 a continuous map. Then, f is called a graph map, if(i)
For each vertexvɛVG1,fv is a vertex in VG2.(ii)
For each edgeeɛEG1,fe is either a vertex or an edge of the graph G2, i.e., feɛVG2orfeɛEG2 [9].(10)
A graph mapf:G1⟶G2 is called a graph folding if and only if f maps vertices to vertices and edges to edges [10].(11)
A graphG is planar if it can be drawn in the plane in such a way that no two edges meet each other except at a vertex to which they are both incident. Any such drawing is called a plane drawing of G. Any plane drawing of G divides the plane into regions called faces.If the edges and vertices of a faceσi of G1 are mapped to the edges and vertices of a face σj of G2, then we write fσi=σj.


## 2. Graph Folding of the Dual Graph

Theorem 1.
LetG1andG2 be graphs and f:G1⟶G2 a graph folding. Consider the graph map g:G1∗⟶G2∗ defined by(i)
For allvi∗∈VG1∗, gvi∗ = vi∗ if and only if fσi=σi, where σi is a face of G1(ii)
Iffσi=σj and fσj=σj where σi and σj are the neighbouring faces, then gvi∗,vj∗ = gvk∗,vj∗ where vk∗ is the vertex of the face σk which is neighbouring to σj but not neighbouring to σi(iii)
Iffσi=σj and fσk=σl, then gvi∗=vi∗ and gvk∗=vj∗ such that each of σi, σk and σj, σl are neighbouring facesProof.
Letf:G1⟶G2 be a graph folding. Suppose that σi, σj, σk, and σl are the faces of the graph G1 such that fσi=σj and fσj=σj where σi and σj are the neighbouring faces. If σk is neighbouring to σj and not neighbouring to σi, then there are no edges joining vi∗ and vk∗ in G1∗, but each of vi∗,vj∗ and vk∗,vj∗ is an edge of G1∗. Thus, by the given definition, g maps edges to edges. Now, let fσi=σj and fσk=σl Then, by the given definition of g, it maps the vertex vi∗ to vl∗ and the vertex vk∗ to vj∗. Now, since each of the faces σi, σk and σj, σl are neighbouring, then each of vi∗,vk∗ and vl∗,vj∗ is an edge of G1∗, i.e., the map g maps edges to edges. And, consequently g is a graph folding of the dual graph of G1.Example 1.
Consider the graphsG1andG2 shown in Figure 1(a). Let f:G1⟶G2 be a graph folding defined by fv6=v1 and fv6,v2,v6,v3,v6,v4,v6,v5=v1,v2,v1,v3,v1,v4,v1,v5, i.e., fσ5,σ6,σ7,σ8=σ1,σ2,σ3,σ4. The graph map g:G1∗⟶G2∗ defined gv5∗,v6∗,v7∗,v8∗=v3∗,v4∗,v1∗,v2∗andv5∗,v1∗,v5∗,v6∗,v5∗,v7∗,v6∗,v2∗,v6∗,v8∗,v7∗,v3∗,v7∗,v8∗,v8∗,v4∗=v3∗,v1∗,v3∗,v4∗,v3∗,v1∗,v4∗,v2∗,v4∗,v2∗,v1∗,v3∗,v1∗,v2∗ is a graph folding, see Figure 1(b). The omitted vertices and edges, or faces, are mapped to themselves through this paper.Figure 1
Graph folding of a graph and its dual graph.
(a)(b)


## 3. Graph Folding of the Gear and the Subdivision Graphs

It should be noted that any graph folding of the wheel graphWn maps the hup into itself.Theorem 2.
LetWn be a wheel graph and Gn be the corresponding gear graph. Let f:Wn⟶Wn be a graph folding. Then, the graph map g:Gn⟶Gn is defined by(i)
gvi,vr = vk,vs and gvr,vj = vs,vl if and only if fvi,vj = vk,vl, where vrandvs are the extra vertices inserting between the adjacent vertices vi,vj and vk,vl, respectively.(ii)
For the hubv, gv = v.Proof.
Letf:Wn⟶Wn be a graph folding, and consider the edges vi,vj, vk,vl∈EWn such that fvi,vj = vk,vl, i.e., fvi = vk and fvj = vl. Now, let vrandvs be the new vertices inserted between the vertices of the edges vi,vj and vk,vl, respectively. Then, we have four new edges vi,vr, vr,vj, vk,vs, and vs,vl∈EGn, but gvi,vr = vk,vs and gvr,vj = vs,vl, i.e., the map g maps edges of Gn to other edges of Gn. Also, for all vi,vk∈VWn if fvi = vk, then g maps the edge vi,v to the edge vk,v where v is the hub, and consequently g is a graph folding of the gear graph Gn.Example 2.
Consider the wheel graphW7 and the corresponding gear graph G7. Let f:W7⟶W7 be a graph folding defined by fv2,v3=v6,v5 and fv2,v1,v2,v3,v2,v7,v3,v4,v3,v7=v6,v1,v6,v5,v6,v7,v5,v4,v5,v7. Then, the graph map g:G7⟶G7 defined by gv8,v2,v9,v3,v10=v13,v6,v12,v5,v11 is a graph folding, see Figure 2. In this case, g maps the edges (v1, v8), (v8, v2), (v2, v7), (v2, v9), (v9, v3), (v3, v7), (v3, v10), and (v10, v4) to the edges (v1, v13), (v13, v6), (v6, v7), (v6, v12), (v12, v5), (v5, v7), (v5, v11), and (v11, v4), respectively.Figure 2
Graph folding of the wheel graphW7 and the gear graph G7.
(a)(b)Definition 1.
For a graphG, if we subdivide each edge once, we get a new graph Gs, and we will call it the subdivision graph.Theorem 3.
LetG be a graph and Gs the subdivision graph of G. Let f:G⟶G be a graph folding defined by for all vi,vj∈EG, fvi,vj = vk,vl∈EG. Then, the graph map g:Gs⟶Gs is defined by(i)
Mapping the edgesvu and uw to themselves if and only if f maps the edge vw to itself(ii)
gvi,ur = vk,us and gur,vj = us,vl where urandus are the new vertices replaced for the edges vi,vj and vk,vl, respectively, is a graph foldingProof.
Suppose thatf:G⟶G is a graph folding such that fvi,vj = vk,vl where vi,vjvk,vl∈EG. Now, replace the edge vi,vj by the new edges vi,urur,vj∈EGs and the edge vk,vl by the new edges vk,usus,vl∈EGs. Since gvi,ur = vk,us and gur,vj = us,vl, then g maps edges to edges of Gs.
Now, lete=vw be an edge of G such that fvw=vw. The subdivision of e replaces e by a new vertex u and two new edges vu and uw. Since gvu=vu and guw=uw, then g maps edges to edges of Gs. Thus, g is a graph folding.Example 3.
Consider the graphG and its subdivision Gs shown in Figure 3. Let f:G⟶G be a graph folding defined by fv1=v3 and fe1,e2=e4,e3. Then, the graph map g:Gs⟶Gs defined by gv1,u1,u2=v3,u4,u3 and ge1′,e2′,e7′,e8′=e4′,e3′,e6′,e5′ is a graph folding.Figure 3
Graph folding of a graph and its subdivision graph.
(a)(b)


## 4. Graph Folding of the Web and Crown Graphs

Theorem 4.
LetCn be a cycle graph, where VCn=v1,…,vn, n is even, and Wn,r be the web graph where VWn,r=v1,…,vn,vn+1,…,v2n,v2n+1,…,v3n,…,vr−1n+1,…,vrn. Let f:Cn⟶Cn be a graph folding defined by for all vi∈VCn, fvi=vj∈VCn. Then, the graph map g:Wn,r⟶Wn,r is defined by(i)
For allvi∈VCn, gvi = fvi = vj(ii)
For allvi+s−1n∈VWn,r, s=2,…,r, then gvi+s−1n = vj+s−1nProof.
LetCn be a cycle graph with even vertices and f:Cn⟶Cn a graph folding defined by for all vi∈VCn, fvi=vj∈VCn. Consider the vertices vi,vj,vk,vl∈VCn such that f maps the edge vi,vk to the edge vj,vl. For the vertices vi∈VCn, gvi = fvi = vj, and hence g is a graph folding. If s = 2, then gvi,vi+n = vj,vj+n and gvi+n,vk+n = vj+n,vl+n, i.e., g maps edges to edges. The same procedure can be done if s=3,4,…,r. Thus, g is a graph folding. For illustration, see Figure 4.Figure 4
The web graph.Example 4.
Consider the cycle graphC4. Let f:C4⟶C4 be a graph folding defined by fv2=v4andfv2,v1,v2,v3=v4,v1,v4,v3. The graph map g:W4,3⟶W4,3 defined by gv2,v6,v10=v4,v8,v12 and gv2,v1,v2,v3,v2,v6,v6,v5,v6,v7,v6,v10,v10,v9,v10,v11=v4,v1,v4,v3,v4,v8,v8,v5,v8,v7,v8,v12,v12,v9,v12,v11 is a graph folding, see Figure 5.Figure 5
Graph folding of the cycle graphC4 and the web graph W4,3.
(a)(b)Theorem 5.
Any crown graphG of 2n vertices can be folded to an edge.Proof.
LetG be a crown graph on 2n vertices, and let A = u1,u2,…,un andB = v1,v2,…,vn be the two sets of vertices of G. Now, a graph folding f:G⟶G can be defined by mapping all the vertices of A to one vertex of A, say ui, and all the vertices of B to one vertex of B, say vj. Thus, the image fG is the edge ui,vj∈EG. Thus, f is a graph folding. For illustration, see Figure 6.Figure 6
Folding crown graphs with six and eight vertices to an edge. (a)f1=u1,u2,u3=u1,f1=v1,v2,v3=v2 and (b) f2=u1,u2,u3,u4=u1,f2=v1,v2,v3,v4=v3.
(a)(b)


## 5. Graph Folding of the Simplex and Crossed Prism Graphs

Theorem 6.
LetG be a graph and f:G⟶G a graph folding. Then, the graph map g:kG⟶kG is defined by(i)
For a zero vertexv∈VkG, if fvi = vk, then gvi,v = vk,v where vi, vk∈VG.(ii)
Ifvi,vj and vk,vl are cliques of G such that fvi,vj = vk,vl, then gvi,vr = vk,vs and gvr,vj = vs,vl where vrandvs are the new vertices of the cliques vi,vj and vk,vl, respectively.(iii)
Ifσ=vi,vj,vk and δ=vl,vm,vn are cliques of G such that fvi,vj,vk = vl,vm,vn, then gu,vrμ = w,vsμ, μ = 1, 2, 3, where uandw are the new vertices of the two cliques σ and δ and vrμandvsμ are the new vertices of the edges of σ and δ, respectively.
And so on.Proof.
LetG be a graph and f:G⟶G a graph folding(i)
Consider the verticesvi, vk∈VG such thatfvi = vk. Let v be a zero vertex of VkG, and then by the given definition of g, it maps the vertex v onto itself. Then, we get new edges vi,v,vk,v∈EkG but gvi,v = vk,v, i.e., g maps edges to edges of kG.(ii)
Consider the cliquesvi,vj and vk,vl of G such that fvi,vj = vk,vl. Let vr and vs be the new vertices of the two cliques, respectively; then we have new four edgesvi,vr, vr,vj, vk,vs, and vs,vl∈EkG but gvi,vr = vk,vs and gvr,vj = vs,vl, i.e., g maps edges to edges.(iii)
Finally, letσ=vi,vj,vk and δ=vl,vm,vn be cliques of G such that fvi,vj,vk = vl,vm,vn. And, considering the new vertices u and w of the two cliques σ and δ, respectively. Then, we have new edges u,vrμw,vsμ∈EkGμ=1,2,3, where vrμ and vsμare the new vertices of the edges of the cliques σ and δ, respectively. Then, the map g maps the new edges of the boundary of σ to the new edges of the boundary of δ according to the rule (ii), and gu,vrμ = w,vsμ where u,vrμw,vsμ∈EkG. For illustration, see Figure 7. Hence, g is a graph folding of the simplex graph kG.Example 5.
LetG be the graph shown in Figure 8(a) and f:G⟶G the graph folding defined by fv3,v6,v8=v1,v4,v7 and fv5,v6,v2,v3,v3,v6,v6,v8,v3,v8=v5,v4,v2,v1,v1,v4,v4,v7,v1,v7. Then, the graph map g:kG⟶kG defined by gv3,v6,v8,u7,u8,u9,u10,u11,w2=v1,v4,v7,u4,u5,u3,u2,u1,w1 and gv3,V,v6,V,v8,V,v5,u8,u8,v6,v2,u7,u7,v3,v3,u9,u9,v6,v6,u10,u10,v8,v3,u11,u11,v8,w2,u9,w2,u10,w2,u11=v1,V,v4,V,v7,V,v5,u5,u5,v4,v2,u4,u4,v1,v1,u3,u3,v4,v4,u2,u2,v7,v1,u1,u1,v7,w1,u3,w1,u2,w1,u1 is a graph folding, see Figure 8(b).Figure 7
The simplex graph.
(a)(b)Figure 8
Graph folding of the simplex graph.
(a)(b)Theorem 7.
LetCn be a cycle graph of even vertices and f:Cn⟶Cn a graph folding. Consider the graph map g:CPn⟶CPn such that for all e∈ECn, ge=fe:(i)
Ifgv2k,v2k+1 = v2k+i,v2k+i+1 whenever fvk,vk+1 = vk+i,vk+i+1, then g is a graph folding(ii)
Ifgv2k,v2k+1 = v2k+i,v2k+1 whenever fvk,vk+1 = vk+i,vk+1, then g is not a graph foldingProof.
(i)
Letf:Cn⟶Cn be a graph folding, and consider the edges vk,vk+1vk+i,vk+i+1∈ECn such thatfvk,vk+1 = vk+i,vk+i+1. Now, ge = fe for all e∈ECn. Also, gv2k,v2k+1 = v2k+i,v2k+i+1, i.e., g maps the edge v2k,v2k+1∈ECPn to the edge v2k+i,v2k+i+1∈ECPn. Consider one of the new edges of CPn, e.g., vk+1,v2k. Then, gvk+1,v2k = vk+i+1,v2k+i∈ECPn, i.e., g maps edges to edges, and hence g is a graph folding.(ii)
Now, letfvk,vk+1 = vk+i,vk+1, and we know that for all e∈ECn, ge = fe. Also, for the edge v2k,v2k+1∈ECPngv2k,v2k+1 = v2k+i,v2k+1∈ECPn, but if we consider one of the new edges of CPn, e.g., vk,v2k+1, then gvk,v2k+1 = vk+i,v2k+1 which is not an edge of CPn, and hence g is not a graph folding.Example 6.
Consider the cycle graphC4, and let f1:C4⟶C4 be a graph folding defined by f1v1=v3 and f1v1,v2,v1,v4=v3,v2v3,v4. The graph map g1:CP4⟶CP4 defined by g1v1,u1=v3,u3 is not a graph folding since g1v1,u2=v3,u2∉ECP4, see Figure 9(a). While if f2:C4⟶C4 is a graph folding defined by f2v1,v2=v3,v4andf2v1,v2,v1,v4,v2,v3=v3,v4,v3,v4,v4,v3, then the graph map g2:CP4⟶CP4 defined by g2v1,v2,u1,u2=v3,v4,u3,u4 and g2v1,v2,v1,v4,v2,v3,u1,u2,u1,u4,u2,u3,v1,u2,v2,u1=v3,v4,v3,v4,v4,v3,u3,u4,u3,u4,u4,u3,v3,u4,v4,u3 is a graph folding, see Figure 9(b).Figure 9
The crossed prism graph may or may not be folded.
(a)(b)


## 6. Graph Folding of the Clique-Sum Graph

We will denote the clique-sum of the two graphsG and H by G cli H.Definition 2.
LetG1, G2, G3, andG4 be graphs. Let f:G1⟶G3 and g:G2⟶G4 be graph maps. Then, we can define a map from the clique-sum of G1 and G2 to the clique-sum of G3 and G4 denoted by fclig:G1cliG2⟶G3cliG4 as follows:
fclige=fe,e∈G1,fe=ge=e,ge,e∈G2, for all edges of the shared cliques.
This map is called the clique-sum map of the mapsf and g.Theorem 8.
LetG1, G2, G3, and G4 be graphs. Let f:G1⟶G3 and g:G2⟶G4 be graph foldings. Then, the clique-sum map fclig:G1cliG2⟶G3cliG4 is a graph folding.Proof.
Supposef and g are graph foldings. Now, let e∈G1cliG2, and then either e∈G1 or e∈G2. In these two cases and since each of f and g is a graph folding, then fclige∈G3cliG4. Thus, fclig maps edges to edges, and hence the clique-sum map is a graph folding.Example 7.
Consider the two graphsG1 and G2 shown in Figure 10(a). Let f:G1⟶G1 be a graph folding defined by fv5=v4,fe7,e8,e9=e4,e5,e6,gv6,v7,v8=v1,v2,v3 and ge17,e18,e12,e16,e10,e11,e13,e14,e15=e1,e3,e3,e1,e3,e2,e2,e1,e2. Then, the clique-sum map fclig:G1cliG2⟶G1cliG2 defined by fcligv5,v6,v7,v8=v4,v1,v2,v3 and fclige7,e8,e9,e17,e18,e12,e16,e10,e11,e13,e14,e15=e4,e5,e6,e1,e3,e3,e1,e3,e2,e2,e1,e2 is a graph folding, see Figure 10(b).Figure 10
Graph folding of the clique-sum graph.
(a)(b)


## 7. Conclusion

We obtained the necessary and sufficient conditions, if exist, for folding new graphs obtained from a given graph by some techniques like dual, gear, subdivision, web, crown, simplex, crossed prism, and clique-sum graphs. We can examine the relation between folding a given pair of graphs and folding of a new graph generated from these given pair of graphs by some operations like join, Cartesian product, normal product, and tensor product. Also, we can lift the definition of folding from graphs to digraphs which has close connections to important industrial applications.



---

*Source: 1316497-2020-12-12.xml*