# The Very Cost Effective Graph Folding of the Join of Two Graphs

^{*}

**Corresponding Author:**El-Kholy EM, Department of Mathematics, Faculty of Science, Tanta University, Tanta, Egypt, Tel: 0403344352, Email: [email protected]

*
Received Date: Oct 11, 2017 /
Accepted Date: Nov 15, 2017 /
Published Date: Nov 21, 2017 *

### Abstract

In this paper, we studied the very cost effective graph property for the join graph of two graphs. In general this is may or may not be a very cost effective graph. We obtained the conditions for the join graph of two graphs to be a very cost effective graph. First we proved that the join graph Pn∨Pm of path graphs is very cost effective graph if n+m is an even number and is not if n+m is an odd number. Then we proved that the join graph of any two cycle graphs Cn and Cm where n, m are both odd is very cost effective, and the join graph Pn∨Cn is a very cost effective graph if n is an odd number. Also we proved that the join graph G1∨G2 of two very cost effective graphs G1 and G2 is a very cost effective graph if n(G1) + n(G2) is even. Finally we proved that the graph folding of the join graph of two very cost effective graphs not always very cost effective but this will be the case if the sum of the numbers of the vertices in the image of the graph folding is even.

**Keywords:**
The join graph; Graph folding; Very cost effective graph

#### Introduction

A graph G=(V,E) is a nonempty, finite set of elements called vertices together with a set of unordered pairs of distinct vertices of G called edges. The vertex set of G is denoted by V (G) and the edge set of G is denoted by E(G). A simple graph is a graph with no loops and no multiple edges. If e={*u*, *v*} is an edge of a graph G, then *u* and *v* are adjacent vertices, while *u* and 𝑒 are incident [1]. Two adjacent vertices are called neighbors of each other. The degree (valency) of a vertex *v* in a graph G is the number of edges incident to *v* [2]. A vertex of degree 0 in G is called an isolated vertex [3]. A vertex v is said to be even or odd, according to whether its degree in G is even or odd [4]. If all the vertices of a graph G have the same valency then it is called a regular graph [5]. The order of G, denoted n(G)=|V(G)|, is the number of vertices in G. The size of G, denoted m(G)=|E(G)|, is the number of edges in G [6]. A graph of order 1 is called a trivial graph, and a graph of order at least 2 is called a non-trivial graph. A graph of size 0 is called an empty graph. A nonempty graph has one or more edges [7]. A graph is said to be connected if every pair of vertices has a path connecting them [8], otherwise is called disconnected. For any vertex *v* ∈ V (G), the open neighborhood of *v* is the set N(*v*)={ *u* ∈ V (G) | *u**v* ∈ E(G)}, and the closed neighborhood of *v* is the set N[*v*]={N(*v*)∪ {*v* }}. For a set S ⊆ V (G), its open neighborhood N(S)=∪*v**ε**S* N(*v*), and its closed neighborhood is N[S]=N(S)∪S. A path *Pn* is graph in which any two vertices are connected by exactly one edge with two vertices of degree 1, and the other n-2 vertices of degree 2.

#### Definition (1.1)

Let G_{1} and G_{2} be simple graphs and f: G_{1}→G_{2} be a continuous function. Then f is called a graph map, if

1. For each vertex v *ε* V(G_{1}), f(v) is a vertex in V(G_{2}).

2. For each edge e *ε* E(G_{1}), dim(f(e)) ≤ dim(e), [4].

#### Definition (1.2)

graph map f: G_{1}→G_{2} is called a graph folding if f maps vertices to vertices and edges to edges, i.e., for each vertex v *ε* V (G_{1}), f(v) is a vertex in V(G_{2}) and for each edge e *ε* E(G_{1}), f(e)is an edge in E(G_{2}) [2].

Cost effective and very cost effective sets in graphs were introduced [6] and studied further [7]. Very cost effective bipartitions were also first introduced [6] and were motivated by the studies of unfriendly partitions [1].

#### Definition (1.3)

A vertex *v* in a set S is said to be cost effective if it is adjacent to at least as many vertices in *V\S* as in S, that is, |N(*v*) ∩ S| ≤ |N(*v*) ∩ (*V\S*)|. A vertex *v* is very cost effective if it is adjacent to more vertices in *V\S* than in S, that is, |N(*v*) ∩ S| < |N(*v*) ∩ (*V\S*)|. A set S is (very) cost effective if every vertex *v* ∈ S is (very) cost effective [6].

#### Definition (1.4)

A bipartition π={S, *V\S*} is called cost effective if each of S and *V\S* is cost effective, and π is very cost effective if each of S and *V\S* is very cost effective. Graphs that have a (very) cost effective bipartition are called (very) cost effective graphs [7].

Note that not every graph has a very cost effective bipartition, e.g., the cycle and the complete graphs of odd orders are not very cost effective.

#### Definition (1.5)

If G_{1} and G_{2} are vertex-disjoint graphs. Then the join, G_{1}V G_{2}, of G_{1} and G_{2} is a super graph of G_{1}+G_{2}, in which each vertex of G_{1} is adjacent to every vertex of G_{2}. The vertex set V(G_{1}V G_{2} )=v_{1}∪v_{2}, [5].

#### The Join Graph of Very Cost Effective Graph

We will study the very cost effective graph property for the join graph of two graphs. First we pay attention to path graphs where any path graph is a very cost effective graph [6]. It should be noted that the join graph *P _{n}* ∨

*P*is not necessary a very cost effective graph. For example

_{m}*P*

_{2}∨

*P*

_{3}and

*P*

_{4}∨

*P*

_{5}are not very cost effective graphs (

**Figure 1**).

In general this is true if n+m is an odd number, as it is proved in theorem (2.3). The following two lemmas give very cost bipartitions for path graphs *P _{n}*, where n is odd or even.

#### Lemma (2.1)

Any path *P _{i}*,

*i*=1,2, …, n where n is even has the only very cost bipartition

*π*={

*S*,

*V\S*}, where

*S*={v

_{1}, v

_{3}, …,

*v*

_{n−1}} and

*V\S*={v

_{2}, v

_{4}, …,

*v*

*n*}. In this case n(

*S*)=n(

*V\S*).

**Proof:** Let *u* be a vertex in *S*, then |*N*(*u*) ∩*S*)|=∅, |*N*(*u*) ∩ (*V\S*)|=1 or 2 (1 for an end vertex and 2 otherwise ) and hence *u* is very cost vertex in *S*. Also, we can prove that *V\S* is a very cost effective set. Hence *π* is a very cost bipartition (**Figure 2a**).

#### Lemma (2.2)

Any path *P _{i}*,

*i*=1,2, …, n where n is odd has the only very cost bipartitions

*π*

_{1}={

*S*

_{1}, V

_{1}\

*S*

_{1}}, where

*S*

_{1}={v

_{1}, v

_{3}, …,

*v*

_{n}} and V

_{1}\

*S*

_{1}={v

_{2}, v

_{4}, …,

*v*

_{n−1}} or

*π*

_{2}={

*S*

_{2}, V

_{2}\

*S*

_{2}}, where

*S*

_{2}={v

_{2}, v

_{4}, …,

*v*

_{n−1}}, V

_{2}\

*S*

_{2}={v

_{1}, v

_{3}, …,

*v*

_{n}}. In this case either n(

*S*

_{1})=n(V

_{1}\

*S*

_{1})+1 or n(V

_{2}\

*S*

_{2})=n(

*S*

_{2})+1.

**Proof:** By the same procedure as lemma (2.1), we can prove this lemma, **Figure 2b**.

#### Theorem (2.3)

The join of any path graphs *Pn* and *P _{m}* where n+

*m*is an odd number is not a very cost effective graph.

**Proof:** Consider two path graphs *Pn* and *P _{m}* with very cost effective bipartitions

*π*

_{1}={

*S*

_{1}, V

_{1}\

*S*

_{1}} and

*π*

_{2}={

*S*

_{2}, V

_{2}\

*S*

_{2}}, where v

_{1}=

*v*(

*P*n) and v

_{2}=

*v*(

*P*). Without loss of generally, we may assume n is even and m is odd, then n(

_{m}*S*

_{1})=n(V

_{1}\

*S*

_{1}) and let n(

*S*

_{2})=n(V

_{2}\

*S*

_{2})+1.

Let *u* be an end vertex in *S*_{1}, then *u* is adjacent to more vertices of V_{1}\*S*_{1} than in *S*_{1} by one. Now consider the join graph *Pn* ∨*P _{m}* with the bipartition

*π*={

*S*,

*V\S*} where

*S*=

*S*

_{1}∪

*S*

_{2}and

*V\S*=(V

_{1}\

*S*

_{1}) ∪(V

_{2}\

*S*

_{2}), the vertex

*u*in this case will be adjacent to all the vertices of

*P*such that n(

_{m}*N*(

*u*)∩

*S*)=n(

*S*

_{2}) and n(

*N*(

*u*) ∩

*V\S*)=n(V

_{2}\

*S*

_{2}). But n(

*S*

_{2})=n(v

_{2}\

*S*

_{2})+1. This mean that the vertex

*u*is adjacent to the same number of the vertices of

*S*

_{2}and V

_{2}\

*S*

_{2}, and thus the join graph

*Pn*⋁

*P*is not a very cost effective graph.

_{m}#### Theorem (2.4)

The join of any path graphs *Pn* and *P _{m}* where n+m an even number is a very cost effective graph.

**Proof:** Consider two path graphs *Pn* and *P _{m}* with very cost effective bipartitions

*π*

_{1}={

*S*

_{1}, V

_{1}\

*S*

_{1}} and

*π*

_{2}={

*S*

_{2}, V

_{2}\

*S*

_{2}}, respectively. We have two cases.

**Case 1:** n and *m* are both even

In this case n(*S*_{1})=n(V_{1}\*S*_{1}) and n(*S*_{2})=n(v_{2}∖*S*_{2}). For any vertex *u* *ε* *P*n, *u* is adjacent to more vertices in V_{1}\*S*_{1} than in *S*_{1}. But u in the join graph *Pn* ∨*P _{m}* will be adjacent to the same numbers of vertices of

*S*

_{2}and V

_{2}\

*S*

_{2}, then

*u*is a very cost effective vertex. This also the case for any vertex

*v*

*ε*

*P*. Then the join graph

_{m}*Pn*⋁

*P*is a very cost effective graph.

_{m}**Case 2:** n and *m* are both odd.

Consider the very cost effective bipartitions *π*_{1} and *π*_{2} where n(*S*_{1})=n(V_{1}\*S*_{1})+1 and (V_{2}\*S*_{2})=n(*S*_{2})+1. Let *u* *ε* *S*_{1} so *u* is adjacent to more vertices in V_{1}\*S*_{1} than in *S*_{1} by at least one (1 or 2).

But in the join graph *Pn* ⋁*P _{m}*, where

*S*=

*S*

_{1}∪

*S*

_{2}and

*V\S*=(V

_{1}\

*S*

_{1}) ∪ (V

_{2}\

*S*

_{2}), the vertex

*u*will be adjacent to all the vertices of V

_{2}\

*S*

_{2}and

*S*

_{2}, so

*u*is adjacent to more vertices of

*V\S*than in

*S*. Thus

*u*is very cost effective vertex. Now, let

*v*

*ε*(V

_{1}\

*S*

_{1}), so

*v*is adjacent to more vertices in

*S*

_{1}than in V

_{1}\

*S*

_{1}by two. But in the join graph

*Pn*⋁

*P*the vertex

_{m}*v*will be adjacent to more vertices of

*S*than in

*V\S*, so

*v*is a very cost effective vertex, and consequently the join graph

*Pn*⋁

*P*is a very cost effective graph.

_{m}#### Theorem (2.5)

The join graphs *P*_{2} ⋁ *P*_{4} and *P*_{3} ⋁ *P*_{5} are very cost effective graphs (**Figure 3**).

In the following we would like to answer the following questions

1. Is every join graph G_{1} ⋁ G_{2} is a much cost?

2. If G_{1} is very cost effective, is G_{1}⋁ G_{2} very cost effective for all graphs?

3. If G_{1} and G_{2} are both very cost effective, is G_{1} v G_{2} very cost effective?

The answer of the first question is, in general, no, i.e., the join G_{1} v G_{2} of non-trivial connected graphs G_{1} and G_{2} may or may not a very cost effective graph. For example, the join graph G_{1}⋁ C_{3} shown in **Figure 4** is not a very cost effective graph while the join graph C_{3}⋁ C_{3} shown in **Figure 5** is a very cost effective graph.

The answer of the first question is yes for the following special case of graphs. Before discussing this case it should be noted that no cycle graph C_{2n+1} of odd order is very cost effective [6].

#### Lemma (2.6)

For a cycle graph *C*_{n}, where n is odd the bipartition *π*={*S*, *V\S*}, where *S*={v_{1}, v_{2}, v_{4}, …, *v*_{n−1}} and *V\S*={v_{3}, v_{5}, …, *v*_{n}} is cost effective. In this case n(*S*)=n(*V\S*)+1.

It is easy to prove the vertex v_{1} ∈*S* is cost effective while the other vertices in both *S* and *V\S* are very cost effective vertices and hence *π* is a cost effective bipartition (**Figure 6**).

Note that the bipartition *π*={*V\S*, *S*} is also a cost bipartition.

#### Theorem (2.7)

The join graph of any two cycle graphs *C*_{n} and *C*_{m} where n, *m* are both odd is a very cost effective graph.

**Proof:** Let *C*_{n} and *C*_{m} be any two cycle graphs where n, *m* are both odd.

Choose the cost effective bipartitions *π*_{1}={*S*_{1}, V_{1}\*S*_{1}} and *π*_{2} ={*S*_{2}, V_{2}\ *S*_{2}} such that n(*S*_{1})=n(V_{1}\*S*_{1})+1 and n(V_{2}\*S*_{2}) =n(*S*_{2})+1. Now consider the join graph *C*_{n} ∨*C*_{m} with the cost bipartition *π*={*S*, *V\S*}, where *S*=*S*_{1} ∪*S*_{2} and *V\S*=(V_{1}\*S*_{1}) ∪ (V_{2}\*S*_{2}). Now, let *u* *ε* *S*_{1}, if *u* is a very cost effective vertex, then *u* must be adjacent to more vertices of V_{1}\*S*_{1} than in *S*_{1} and since *u* is adjacent to all the vertices of *S*_{2} and V_{2}\*S*_{2} and n(*S*_{2})=n(v_{2}\ *S*_{2})−1, then *u* is still a very cost effective vertex in the join graph *C*_{n} ⋁*C*_{m}. Now, suppose *u* *ε* *S*_{1} is a cost effective vertex, then *u* will be adjacent to at least as many vertices in V_{1}\*S*_{1} as in *S*_{1} and since *u* is adjacent to all the vertices of *S*_{2} and V_{2}\*S*_{2} and n(V_{2}\*S*_{2})=n(*S*_{2})+1. Thus *u* is adjacent to more vertices in *S* than in *V\S* by at least one and consequently *u* is a very cost effective vertex. Now, let *u* *ε* (V_{1}\*S*_{1}), then *u* must be adjacent to more vertices in *S*_{1} than in V_{1}\*S*_{1} certainly by at least two and since *u* is adjacent to all the vertices of *S*_{2} and (V_{2}\*S*_{2}) and n(*S*_{2})=n(V_{2}\*S*_{2})−1, then u is still a very cost effective vertex in the join graph *C*_{n} ⋁*C*_{m}. Also, we can prove that any vertex of *S*_{2} or V_{2}\*S*_{2} is a very cost effective vertex and hence *π* is a very cost bipartition, i.e., *C*_{n} ∨*C*_{m} is a very cost effective graph.

#### Theorem (2.8)

The join graph *C*_{3} ⋁*C*_{5} is a very cost effective graph (**Figure 7**).

Now let *G*_{1} be a very cost effective graph and *G*_{2} any non-trivial connected graph. The join graph of *G*_{1} ⋁*G*_{2} is not always very cost effective; the following example illustrates this fact.

#### Theorem (2.9)

The join graph *C*_{3} ⋁*C*_{4} shown in **Figure 8a** is not a very cost effective graph while the join graph *P*_{3} ⋁*C*_{3} is very cost effective (**Figure 8b**).

Thus the answer of the second question is, in general, no. The answer is yes in the following case.

**Theorem (2.10)**

The join graph of any path *P _{n}* and cycle

*C*

_{n}where n is odd is a very cost effective graph.

**Proof: **By the same procedure as in theorem (2.7) we can prove this theorem.

Now, we come to the third question. The answer of the third question is also, in general, no, i.e., if G_{1} and G_{2} are two very cost effective graphs, then the join graph *G*_{1} ⋁*G*_{2} may or may not be very cost effective. For example, if G_{1} and G_{2} are the very cost effective graphs shown in **Figure 9**, then the join graph *G*_{1} ⋁*G*_{2} is not very cost effective.

While the join graph *K*_{4} ⋁*K*_{,22} is a very cost effective graph (**Figure 10**).

The following theorem gives the condition for which the join graph of two very cost effective graphs is very cost effective.

#### Theorem (2.11)

The join graph of two non- trivial connected very cost effective graphs *G*_{1} and *G*_{2} is a very cost effective graph if n(*G*_{1})+n(*G*_{2}) is even.

**Proof:** Let *G*_{1} and *G*_{2} be any non-trivial connected graphs, we have two cases

(1) n(*G*_{1}) and n(*G*_{2}) are both even. Then each graph has a very cost effective bipartition. Let *π*_{1}={*S*_{1}, V_{1}\*S*_{1}} and *π*_{2}={*S*_{2}, V_{2}\*S*_{2}}, be such that n(*S*_{1})=n(V_{1}\*S*_{1}) and n(*S*_{2})=n(V_{2}\*S*_{2}). Now consider the join graph *G*_{1} ∨*G*_{2} with the cost bipartition *π*={*S*, *v*\*S*}, where *S*=*S*_{1} ∪ *S*_{2} and *v*\*S*=(V_{1}\*S*_{1}) ∪ (V_{2}\*S*_{2}). Let *u* *ε* *S*_{1}, then *u* is adjacent to more vertices of V_{1}\*S*_{1} than in *S*_{1} and since *u* is adjacent to all the vertices of *S*_{2} and V_{2}\*S*_{2}, then *u* is still a very cost effective vertex in the join graph *G*_{1} ∨*G*_{2}. Also we can prove that any vertex of V_{1}\*S*_{1} or *S*_{2} or V_{2}\*S*_{2} is a very cost effective vertex and hence *π* is a very cost effective bipartition, i.e., *G*_{1} ∨*G*_{2} is a very cost effective graph.

(2) n(*G*_{1}) and n(*G*_{2}) are both odd. Suppose that *π*_{1}={*S*_{1}, V_{1}\*S*_{1}} and *π*_{2}={*S*_{2}, V_{2}\*S*_{2}} are very cost effective bipartitions such that n(*S*_{1})=n(v_{1}\ *S*_{1})+1 and n(V_{2}\*S*_{2})=n(*S*_{2})+1. Let *π*={ *S*, *v*\*S*} be a cost bipartition of the join graph *G*_{1} ∨*G*_{2}, where *S*=*S*_{1} ∪*S*_{2} and *v*\*S*=(V_{1}\*S*_{1}) ∪ (V_{2}\*S*_{2}). Now, let *u* *ε* *S*_{1}, then *u* must be adjacent to more vertices of V_{1}\*S*_{1} than in *S*_{1} and since *u* is adjacent to all the vertices of *S*_{2} and V_{2}\*S*_{2} and n(*S*_{2})=n(v_{2}\ *S*_{2})−1, then *u* is still a very cost effective vertex in the join graph *G*_{1} ∨*G*_{2}. Now, let *u* *ε* V_{1}\*S*_{1}, then *u* must be adjacent to more vertices in *S*_{1} than in V_{1}\*S*_{1} certainly by at least two and since *u* is adjacent to all the vertices of *S*_{2} and V_{2}\*S*_{2}, then *u* is adjacent to more vertices in *S* than in *v*\*S* by at least one and *u* is a very cost effective vertex in the join graph *G*_{1} ⋁*G*_{2}. Also we can prove that any vertex of *S*_{2} or V_{2}\*S*_{2} is very cost effective vertex and hence *π* is a very cost effective bipartition, i.e., *G*_{1} ⋁*G*_{2} is a very cost effective graph.

#### Theorem (2.12)

1) The join graph *C*_{4} ⋁*W*_{1,3} of the very cost effective graphs *C*_{4} and *W*_{1,3} is once again is a very cost effective graph (**Figure 11**).

2) Let *G*_{1} and *G*_{2} be the very cost effective graphs shown in **Figure 12**. Then the join graph *G*_{1} ⋁*G*_{2} is also very cost effective graph (**Figure 12**).

#### The Join Graph Folding of Very Cost Effective Graphs

In this section we study very cost effective graph folding of a new graph obtained by the join of two other graphs.

#### Definition (3.1)

Let G_{1}=(V_{1}, *E _{1}*), G

_{2}=(V

_{2},

*E*

_{2}),

*G*=(V

_{3}_{3}, E

_{3}) and

*G*=(V

_{4}_{4}, E

_{4}) be graphs. Let f: G

_{1}→

*G*and g: G

_{3}_{2}→

*G*be graph maps. A join map fV g: G

_{4}_{1}V G

_{2}→

*G*V

_{3}*G*is a map defined by

_{4}For each vertex

For each edge e=(v_{1},v_{2}), v_{1} ∈ V_{1} and v_{2} ∈ v_{2}, (f⋁ g){e}={f(v_{1}),g(v_{2})} ∈ *G _{3}* ⋁

*G*.

_{4}If e=(u_{1}, v_{1})∈*E _{1}*, then (f ⋁ g){e}={f(u

_{1}), f(v

_{1})}, also if e=(u

_{2}, v

_{2})∈

*E*

_{2}, then (f ⋁ g){e}=(f ⋁ g){(u

_{2}, v

_{2})}={ g(u

_{2}), g(v

_{2})} [3].

#### Definition (3.2)

A graph folding f: G_{1}→G_{2} between two graphs G_{1} and G_{2} is a very cost effective graph folding if the image f(G_{1})=H ⊆ G_{2} is a very cost effective graph [8].

It should be noted that the image of a graph folding f: G→G of a very cost effective graph G may or may not be a very cost effective graph

e.g., if G is the cycle graph C_{4} where V(C_{4})={u_{1}, u_{2}, u_{3}, u_{4}} and E(C_{4})={e_{1}, e_{2}, e_{3}, e_{4}} then the graph folding f: C_{4}→C_{4} defined by f{u_{1}, u_{2}, u_{3}, u_{4}}={u_{3}, u_{2}, u_{3}, u_{4}} and f{e_{1}, e_{2}, e_{3}, e_{4}}={e_{4}, e_{3}, e_{3}, e_{4}} is a very cost effective graph folding since the image is P_{3} (**Figure 13**).

From now on the omitted vertices or edges will be mapped into themselves. Also if G is the very cost effective graph shown in **Figure 14** where V(G)={*v _{1}*,

*v*, v

_{2}_{3}, v

_{4}} and E(G)={e

_{1}, e

_{2}, e

_{3}, e

_{4}, e

_{5}} then the graph folding g: G→G defined by g{

*v*}={v

_{1}_{3}} and g{e

_{1}, e

_{2}}={e

_{4}, e

_{3}} is not a very cost effective.

Once again if f and g are both very cost effective graph foldings, the join map (f ∨ g) may or may not be a very cost effective graph folding. The following two theorems illustrate this.

#### Theorem (3.3)

Let G_{1}=P_{3} and G_{2}=P_{4} as shown in **Figure 15**. Let f : G_{1}→G_{1} and g: G_{2}→G_{2} be the very cost effective graph foldings defined by f{*v _{1}*}={v

_{3}}, f{e

_{1}}={e

_{2}} and g{u

_{1}, u

_{4}}={u

_{3}, u

_{2}} and g{e

_{3}, e

_{5}}={e

_{4}, e

_{4}}. The join graph folding f ∨g: G

_{1}⋁G

_{2}→G

_{1}⋁G

_{2}defined by (f⋁g){u

_{1}, u

_{4}, v

_{1}}={u

_{3}, u

_{2}, v

_{3}} is a very cost effective graph folding.

#### Theorem (3.4)

Let G_{1} and G_{2} be any connected graphs and f, g are very cost effective graph foldings of G_{1} and G_{2}, respectively. Then (f⋁g)(G_{1}⋁G_{2}) is a very cost effective graph folding if no. V(f(G_{1}))+no. V(g(G_{2})) is even. The proof is almost the same as the proof of theorem (2.11).

#### Theorem (3.5)

Consider the wheel graphs W_{1,4} and W_{1,6} shown in **Figure 16**. Let f: W_{1,4}→W_{1,4} and g: W_{1,6}→W_{1,6} be the very cost effective graph folding defined By f{u_{1}}={u_{3}} and f{e_{1}, e_{4}, e_{5}}={e_{2}, e_{3}, e_{7}} and g{v_{1}, v_{5}, v_{6}}={v_{3}, v_{3}, v_{4}} and g{e_{1}, e_{4}, e_{5}, e_{6}, e_{7}, e_{11}, e_{1}_{2}}={e_{2}, e_{3}, e_{4}, e_{3}, e_{9}, e_{9}, e_{1}_{0}}. Then The join graph folding f ∨g: W_{1,4} ∨ W_{1,6}→W_{1,4} ∨ W_{1,6} is a very cost effective graph folding (**Figure 16**).

#### References

- Aharoni R, Milner EC, Prikry K (1990) Unfriendly partitions of a graph. Journal of Combinatorial Theory, Series B 50: 1-10.
- El-Kholy E, Al-Esawy A (2005) Graph folding of some special graphs. Journal of Mathematics and Statistics 1: 66-70.
- El-Kholy E, Al-Esawy A (2015) Operations on graphs and graph folding. Bulletin of Mathematics and Statistical Research 3: 190-201.
- Erdos P (1959) Graph Theory and probability. Canadian Mathematical Bulletin 11: 34-38.
- Harary F (1969) Graph Theory. Addison-Wesley.
- Haynes TW, Hedetniemi SM, Hedetniemi ST, McCoy TL, Vasylieva L (2012) Cost effective domination in graphs. Congr Numer 211: 197-209.
- Haynes TW, Hedetniemi ST, Vasylieva I (2015) Very cost effective bipartitions in graphs. AKCE International Journal of Graphs and Combinatorics 12: 155-160.
- Zeen El-Deen MR, AL-Esawy A. On very cost effective graphs and its folding.

Citation: El-Kholy EM, Mohamed HA (2017) The Very Cost Effective Graph Folding of the Join of Two Graphs. J Appl Computat Math 6: 375. Doi: 10.4172/2168-9679.1000375

Copyright: ©2017 El-Kholy EM, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.