I. INTRODUCTION

Let $G=(V,E)$ be a graph, where $V$ is the set of its vertices and $E$ is the set of its edges. Two distinct vertices $u,v\in V$ are called independent if $\{u,v\}$ is not an edge in $G$. Two vertices $u,v$ are called neighbors (adjacent) if $\{u,v\}$ is an edge in $G$. The degree (valency) of a vertex is the number of edges with the vertex as an end point. A graph with no loops or multiple edges is called a simple graph. A graph is said to be connected if every pair of vertices has a path connecting them otherwise the graph is disconnected. A graph $H=(V^{\prime },E^{\prime })$ is called induced subgraph of $G=(V,E)$ if $V^{\prime }\subseteq V$ and $\{u,v\}$ is an edge in $H$ wherever $u$ and $v$ are distinct vertices in $V^{\prime }$ and $\{u,v\}$ is an edge in $G$, $H$ is called proper if $H\ne G$. A cycle graph is a graph that consists of a single cycle, or in other words, some number of distinct vertices connected in a closed chain. The cycle graph with $n$ vertices is denoted by $C_n$. The number of vertices in $C_n$ equals the number of edges, and every vertex has degree 2. The wheel graph $W_n$ or $n$ -wheel is a graph that contains a cycle of order $n-1$, and for which every graph vertex in the cycle is connected to one other graph vertex which is called the hub. A bipartite graph is a graph whose vertex set can be split into two sets A and B in such a way that each edge of the graph joins a vertex in A to a vertex in B. A vertex coloring of a graph $G=(V,E)$ is a way of coloring the vertices of the graph such that no two adjacent vertices share the same color. A clique of a graph G is a maximal complete subgraph. In this case each pair of vertices of the clique are adjacent. The clique number $W(G)$ of a graph is the number of graph vertices in the largest clique of G, [8]. The clique number of a cycle graph $C_n$, n odd is 3 and 2 otherwise. For a wheel graph $W_n$, n is even the clique number is 4 and is 3 otherwise. The chromatic number of a graph G is the smallest number of colors needed to color the vertices of a graph G so that no two adjacent vertices share the same color, and is often denoted by $\chi (G)$. A graph G is called perfect if for every induced subgraph H of G, $\chi (H)=W(H)$. Note that if G is a perfect graph, then every induced subgraph of G is also perfect,[2].

II. PERFECT FOLDING

Definition (2-1)

Ref

Let $G_1$ and $G_2$ be two simple graphs and $f:G_1\to G_2$ be continuous map. Then $f$ is called a graph map, if (i) For each vertex $v\in V(G_1)$, $f(v)$ is a vertex in $V(G_2)$.

(ii) For each edge $e\in E(G_1)$, $dim(f(e))\le dim(e)$, [3].

Definition (2-2)

A graph map $f:G_1\to G_2$ is called a graph folding if and only if f maps vertices to vertices and edges to edges, i.e., if (i) For each vertex $v\in V(G_1)$, $f(v)$ is a vertex in $V(G_2)$.

(ii) For each edge $e\in E(G_1)$, $f(e)$ is an edge in $E(G_2)$, [4].

Note that if the vertices of an edge $e=(u,v)\in E(G_I)$ are mapped to the same vertex, then the edge e will collapse to this vertex and hence we cannot get a graph folding. In other words, any graph folding cannot maps edges to loops but it may map loops, if there is any, to loops.

Definition(2-3)

Let $G$ and $H$ be simple connected graphs. We call a graph folding $f:G\to H$ perfect folding if its image $f(G)$ is a perfect subgraph of $H$.

In general the image of a graph folding $f:G\to H$ is not a perfect graph e.g., if $G_1$ is the imperfect graph shown in Fig.(1-a), where $V(G_1)=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$ and $E(G_1)=\{e_1,e_2,e_3,e_4,e_5,e_6,e_7\}$. Then the graph folding $f:G_1\to G_1$ defined by $f\{v_6,v_7\}=\{v_5,v_4\}$ and $f\{e_6,e_7\}=\{e_2,e_4\}$ is not a perfect folding. While if we consider the imperfect graph $G_2$ shown in Fig.(1-b), where $V(G_2)=\{u_1,...,u_7\}$ and $E(G_2)=\{e_1,...,e_7\}$.

Then the graph folding $g:G_2\to G_2$ defined by $g\{u_1,u_4\}=\{u_6,u_6\}$ and $g\{e_4,e_7\}=\{e_5,e_6\}$ is a perfect folding. The omitted vertices and edges in this example and through the paper will be mapped to themselves.

(a)

$g(G_2)$Figure 1

Theorem (2-4)

Let G be a simple connected graph such that the number of $E(G)\ge 2$. If the chromatic number $\chi (G)$ is equal to two, then G can be perfectly folded.

Proof From [5], any simple connected graph G such that $E(G)\ge 2$ and $\chi (G)=2$ can be folded to an edge. In this case $\chi (f(G))=W(f(G))=2$, and thus the graph G can be perfectly folded to an edge.

Example (2-5)

The cubic graph G with $\chi (G)=W(G)=2$, shown in Fig. (2) can be folded to an edge by the graph folding $f(v_1,\dots ,v_8)=(v_1,v_2,v_1,v_2,v_1,v_2,v_1,v_2)$. This folding can be done by the composition of a sequence of foldings $f_1,f_2,f_3$ and $f_4$, see Fig.(2). And hence the graph folding is a perfect.

Figure 2 Lemma (2-6)

Any folding of a bipartite graph (complete) is a perfect folding. Proof

This follows from the fact that the chromatic number of a bipartite graph is equal to two, and thus it can be perfectly folded.

Example (2-7)

Consider the bipartite graph G shown in Fig.(3). A graph folding $f:G\to G$ defined by $f\{v_1,v_3\}=\{v_2\}$ and $f\{e_1,e_4\}=\{e_2,e_3\}$ is a perfect folding.

Figure 3 III. PERFECT FOLDING OF CYCLE GRAPHS

The chromatic number of a cycle graph $C_n$, n > 2 where n is odd is 3 while that for n even is 2, [1].

Theorem (3-1)

Any folding of a cycle graph $C_n$ of an even number of edges is a perfect folding.

Proof

This follows from the fact that $\chi (C_n)$, n is an even number is equal to two. Thus $C_n$ can be perfectly folded.

Example (3-2)

Consider the cycle graph $C_4$ where $\chi (C_4)=W(C_4)=2$, the graph folding $f:C_4\to C_4$ defined by $f\{v_1,v_4\}=\{v_3,v_2\}$ and $f\{e_i\}=\{e_3\}$, i=1,2,4 is a perfect folding, see Fig.(4).

It should be noted that the cycle graph $C_3$ cannot be folded, [4].

Theorem (3-3)

Let $G=C_n$, be a cycle graph of an odd number of edges (vertices). Then $G$ can be perfectly folded to $C_3$.

Since $G=C_n$ has an odd number of edges (vertices). Thus the graph $C_n$ has three color classes, say $V_1$, $V_2$ and $V_3$. We can color the vertices of $C_n$ alternatively with the two colors of $V_1$ and $V_2$ except the last two edges one will join a vertex colored by the color of $V_2$ and a vertex colored by the color of $V_3$ and the other edge will join a vertex colored by the color of $V_3$ and a vertex colored by the color of $V_1$. Thus the number of vertices of color class $V_1=$ the number of vertices color class

$V_2=(n-1)/2$, but $V_3$ has only one vertex w. We can define a graph folding $f:C_n\to C_n$, n is odd, by mapping vertices of $V_1$ to a vertex of $V_1$, say u, and mapping the vertices of $V_2$ to a vertex of $V_2$, say v, finally mapping w into itself. Thus we have three vertices u, v, w and hence three edges in the image i.e., we have $C_3$. But $\chi (C_3)=W(C_3)=3$, i.e., the graph folding f is perfect.

Example (3-4)

Let $G=C_5$ and $h:G\to G$ be the graph folding defined by $h\{v_5,v_4\}=\{v_3,v_1\}$ and $h\{e_i\}=\{e_2\}$, $i=3,4$ is a perfect folding, see Fig.(5). This can be done by the composition of the two graph foldings $h_1:C_5\to C_5$ defined by $h_1\{v_5\}=\{v_3\}$, $h_1\{e_3\}=\{e_4\}$ and $h_2:h_1(C_5)\to h_1(C_5)$ defined by $h_2\{v_4\}=\{v_1\}$, $h_2\{e_4\}=\{e_2\}$.

Figure 5 IV. PERFECT FOLDING OF WHEEL GRAPHS

The chromatic number of a wheel graph $W_n$ if n is odd is 3 and 4 if n is even, [1].

Theorem (4-1)

Any wheel graph $W_n$ of an odd number of vertices can be perfectly folded to $C_3$.

A wheel graph $W_n$ of order n, n is an odd number, is a graph that contains a cycle of even order n - 1, and each vertex in the cycle is

Ref connected to the hub. In this case the chromatic number $\chi (W_n)=3$, thus the graph $W_n$ can be colored by using three colors A, B and C. One color for the hub, say A, and the vertices of the even cycle $C_{n-1}$ can be colored alternatively with two colors B and C, i.e., if the set of vertices of the cycle $C_{n-1}$ is $V(C_{n-1})=\{v_1,v_2,...,v_{n-1}\}$, then the colors B and C have the following vertices, $B=\{v_1,v_3,...,v_{n-2}\}$ and $C=\{v_2,v_4,...,v_{n-1}\}$. Now we can define a graph folding by mapping the vertices of B to a vertex of B, the vertices of C to a vertex of C and the hub onto itself. The image of this map will contain three vertices, three edges and thus we have $C_3$, i.e., the graph folding is perfect.

Example (4-2)

Consider the wheel graph $W_7$ and the graph folding $f:W_7\to W_7$ defined by $f\{v_i\}=\{v_1\}$, i=3,5, $f\{v_j\}=\{v_2\}$, j=4,6 and $f\{e_k\}=\{e_1,e_1,e_1,e_1,e_1,e_1,e_7,e_8,e_7,e_8,e_7,e_8\}$, k=1,...,12. This graph folding is perfect, see Fig.(6).

It should be noted that the wheel graph of an even number of vertices cannot be folded, [4], and hence cannot be perfectly folded.

V. THE CLIQUE NUMBER AND PERFECT FOLDING

The chromatic number of any graph is equal to or greater than its clique number, i.e., $\chi (G)\ge W(G)$. For connected graphs $2\le W(G)\le \chi (G)\le n$, where n is the number of vertices of the graph G, [7].

Theorem (5-1)

Let G be a simple connected graph, if the clique number $W(G)$ equal to the chromatic number $\chi (G)$ equal to 2 and $E(G)\ge 2$, then the graph G can be perfectly folded.

It is immediately follows from Theorem (2-4) and since $\chi (G)=2$, then G can be perfectly folded.

Example (5-2)

Consider the cycle graph $C_6$ shown in Fig.(7). A graph folding $f:C_6\to C_6$ defined by $f\{v_2,v_3,v_4,v_5\}=\{v_6,v_1,v_6,v_1\}$ and $f\{e_i\}=\{e_6\}$, $i=1,\dots ,5$ is a perfect folding.

Theorem (5-3)

Let $G$ be a simple connected graph such that no. $V(G)=n$. If , then the graph can be perfectly folded to a clique of order $k$.

Proof

Let $W(G)=\chi (G)=k$, then we have a maximal complete subgraph of $k$ vertices. This complete graph cannot be folded, [3]. These vertices must be colored by different colors $A_1,A_2,\dots ,A_k$. Now the other $(n-k)$ vertices of $G$, will be colored by the colors $A_1,\dots ,A_m$, $m\le k$ in such a way that any edge will joins two vertices of different colors. So we can define a sequence of graph folding $f_i:G\to G_i$, where $G_i=f_i(G_{i-1})$, $i=1,\dots ,m$, $G_0=G$, by mapping the $(n-k)$ vertices to other vertices but of the same color, until we get the $k$ -clique which cannot be folded any more. And hence $W(f_i(G_i))=\chi (f_i(G_i))=k$, i.e., the graph folding is a perfect.

Example (5-4)

Consider the house graph G with 5 vertices and 6 edges shown in Fig.(8), where . This graph can be folded to a triangle by the graph folding $f:G\to G$ defined by $f\{v_4,v_5\}=\{v_2,v_3\}$ which is a perfect folding.

Notes