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

ISSN: 2168-9679

Journal of Applied & Computational Mathematics

Reach Us +44-1522-440391

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

El-Kholy EM1* and Mohamed HA2
1Department of Mathematics, Faculty of Science, Tanta University, Tanta, Egypt
2Department of Mathematics, Faculty of Engineering at Shoubra, Benha University, Banha, Egypt
*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) | uv ∈ 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 G1 and G2 be simple graphs and f: G1→G2 be a continuous function. Then f is called a graph map, if

1. For each vertex v ε V(G1), f(v) is a vertex in V(G2).

2. For each edge e ε E(G1), dim(f(e)) ≤ dim(e), [4].

Definition (1.2)

graph map f: G1→G2 is called a graph folding if f maps vertices to vertices and edges to edges, i.e., for each vertex v ε V (G1), f(v) is a vertex in V(G2) and for each edge e ε E(G1), f(e)is an edge in E(G2) [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 G1 and G2 are vertex-disjoint graphs. Then the join, G1V G2, of G1 and G2 is a super graph of G1+G2, in which each vertex of G1 is adjacent to every vertex of G2. The vertex set V(G1V G2 )=v1∪v2, [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 PnPm is not necessary a very cost effective graph. For example P2P3 and P4P5 are not very cost effective graphs (Figure 1).

computational-mathematics-effective-graphs

Figure 1: P2P4 and P3P5 cost effective graphs.

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 Pn, where n is odd or even.

Lemma (2.1)

Any path Pi, i=1,2, …, n where n is even has the only very cost bipartition π={S, V\S}, where S={v1, v3, …, vn−1} and V\S={v2, v4, …, vn}. 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).

computational-mathematics-bipartition-cost

Figure 2: Bipartition cost effective graphs.

Lemma (2.2)

Any path Pi, i=1,2, …, n where n is odd has the only very cost bipartitions π1={S1, V1\S1}, where S1={v1, v3, …, vn} and V1\S1={v2, v4, …, vn−1} or π2={S2, V2\S2}, where S2={v2, v4, …, vn−1}, V2\S2={v1, v3, …, vn}. In this case either n(S1)=n(V1\S1)+1 or n(V2\S2)=n(S2)+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 Pm where n+m is an odd number is not a very cost effective graph.

Proof: Consider two path graphs Pn and Pm with very cost effective bipartitions π1={S1, V1\S1} and π2={S2, V2\S2}, where v1=v(Pn) and v2=v(Pm). Without loss of generally, we may assume n is even and m is odd, then n(S1)=n(V1\S1) and let n(S2)=n(V2\S2)+1.

Let u be an end vertex in S1, then u is adjacent to more vertices of V1\S1 than in S1 by one. Now consider the join graph PnPm with the bipartition π={S, V\S} where S=S1S2 and V\S=(V1\S1) ∪(V2\S2), the vertex u in this case will be adjacent to all the vertices of Pm such that n(N(u)∩S)=n(S2) and n(N(u) ∩V\S)=n(V2\S2). But n(S2)=n(v2\ S2)+1. This mean that the vertex u is adjacent to the same number of the vertices of S2 and V2\S2, and thus the join graph PnPm is not a very cost effective graph.

Theorem (2.4)

The join of any path graphs Pn and Pm where n+m an even number is a very cost effective graph.

Proof: Consider two path graphs Pn and Pm with very cost effective bipartitions π1={S1, V1\S1} and π2={S2, V2\S2}, respectively. We have two cases.

Case 1: n and m are both even

In this case n(S1)=n(V1\S1) and n(S2)=n(v2S2). For any vertex u ε Pn, u is adjacent to more vertices in V1\S1 than in S1. But u in the join graph PnPm will be adjacent to the same numbers of vertices of S2 and V2\S2, then u is a very cost effective vertex. This also the case for any vertex v ε Pm. Then the join graph PnPm is a very cost effective graph.

Case 2: n and m are both odd.

Consider the very cost effective bipartitions π1 and π2 where n(S1)=n(V1\S1)+1 and (V2\S2)=n(S2)+1. Let u ε S1 so u is adjacent to more vertices in V1\S1 than in S1 by at least one (1 or 2).

But in the join graph PnPm, where S=S1S2 and V\S=(V1\S1) ∪ (V2\S2), the vertex u will be adjacent to all the vertices of V2\S2 and S2, so u is adjacent to more vertices of V\S than in S. Thus u is very cost effective vertex. Now, let v ε (V1\S1), so v is adjacent to more vertices in S1 than in V1\S1 by two. But in the join graph PnPm the vertex 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 PnPm is a very cost effective graph.

Theorem (2.5)

The join graphs P2P4 and P3P5 are very cost effective graphs (Figure 3).

computational-mathematics-effective-graphs

Figure 3: P2P4 and P3P5 are very cost effective graphs.

In the following we would like to answer the following questions

1. Is every join graph G1 ⋁ G2 is a much cost?

2. If G1 is very cost effective, is G1⋁ G2 very cost effective for all graphs?

3. If G1 and G2 are both very cost effective, is G1 v G2 very cost effective?

The answer of the first question is, in general, no, i.e., the join G1 v G2 of non-trivial connected graphs G1 and G2 may or may not a very cost effective graph. For example, the join graph G1⋁ C3 shown in Figure 4 is not a very cost effective graph while the join graph C3⋁ C3 shown in Figure 5 is a very cost effective graph.

computational-mathematics-cost-effective

Figure 4: G1 V C3 is not very cost effective.

computational-mathematics-cost-effective

Figure 5: C3 V C3 is a very cost effective.

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 C2n+1 of odd order is very cost effective [6].

Lemma (2.6)

For a cycle graph Cn, where n is odd the bipartition π={S, V\S}, where S={v1, v2, v4, …, vn−1} and V\S={v3, v5, …, vn} is cost effective. In this case n(S)=n(V\S)+1.

It is easy to prove the vertex v1S 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).

computational-mathematics-cost-effective

Figure 6: v1S is cost effective.

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

Theorem (2.7)

The join graph of any two cycle graphs Cn and Cm where n, m are both odd is a very cost effective graph.

Proof: Let Cn and Cm be any two cycle graphs where n, m are both odd.

Choose the cost effective bipartitions π1={S1, V1\S1} and π2 ={S2, V2\ S2} such that n(S1)=n(V1\S1)+1 and n(V2\S2) =n(S2)+1. Now consider the join graph CnCm with the cost bipartition π={S, V\S}, where S=S1S2 and V\S=(V1\S1) ∪ (V2\S2). Now, let u ε S1, if u is a very cost effective vertex, then u must be adjacent to more vertices of V1\S1 than in S1 and since u is adjacent to all the vertices of S2 and V2\S2 and n(S2)=n(v2\ S2)−1, then u is still a very cost effective vertex in the join graph CnCm. Now, suppose u ε S1 is a cost effective vertex, then u will be adjacent to at least as many vertices in V1\S1 as in S1 and since u is adjacent to all the vertices of S2 and V2\S2 and n(V2\S2)=n(S2)+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 ε (V1\S1), then u must be adjacent to more vertices in S1 than in V1\S1 certainly by at least two and since u is adjacent to all the vertices of S2 and (V2\S2) and n(S2)=n(V2\S2)−1, then u is still a very cost effective vertex in the join graph CnCm. Also, we can prove that any vertex of S2 or V2\S2 is a very cost effective vertex and hence π is a very cost bipartition, i.e., CnCm is a very cost effective graph.

Theorem (2.8)

The join graph C3C5 is a very cost effective graph (Figure 7).

computational-mathematics-cost-effective

Figure 7: C3 V C3 is very cost effective.

Now let G1 be a very cost effective graph and G2 any non-trivial connected graph. The join graph of G1G2 is not always very cost effective; the following example illustrates this fact.

Theorem (2.9)

The join graph C3C4 shown in Figure 8a is not a very cost effective graph while the join graph P3C3 is very cost effective (Figure 8b).

computational-mathematics-cost-effective

Figure 8: (a) C3 V C4 is not cost effective; (b): P3 V C3 is very cost effective.

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 Pn and cycle Cn 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 G1 and G2 are two very cost effective graphs, then the join graph G1G2 may or may not be very cost effective. For example, if G1 and G2 are the very cost effective graphs shown in Figure 9, then the join graph G1G2 is not very cost effective.

computational-mathematics-cost-effective

Figure 9: G1G2 is not very cost effective.

While the join graph K4K,22 is a very cost effective graph (Figure 10).

computational-mathematics-cost-effective

Figure 10: K4K,22 is a very cost effective graph.

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 G1 and G2 is a very cost effective graph if n(G1)+n(G2) is even.

Proof: Let G1 and G2 be any non-trivial connected graphs, we have two cases

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

(2) n(G1) and n(G2) are both odd. Suppose that π1={S1, V1\S1} and π2={S2, V2\S2} are very cost effective bipartitions such that n(S1)=n(v1\ S1)+1 and n(V2\S2)=n(S2)+1. Let π={ S, v\S} be a cost bipartition of the join graph G1G2, where S=S1S2 and v\S=(V1\S1) ∪ (V2\S2). Now, let u ε S1, then u must be adjacent to more vertices of V1\S1 than in S1 and since u is adjacent to all the vertices of S2 and V2\S2 and n(S2)=n(v2\ S2)−1, then u is still a very cost effective vertex in the join graph G1G2. Now, let u ε V1\S1, then u must be adjacent to more vertices in S1 than in V1\S1 certainly by at least two and since u is adjacent to all the vertices of S2 and V2\S2, 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 G1G2. Also we can prove that any vertex of S2 or V2\S2 is very cost effective vertex and hence π is a very cost effective bipartition, i.e., G1G2 is a very cost effective graph.

Theorem (2.12)

1) The join graph C4W1,3 of the very cost effective graphs C4 and W1,3 is once again is a very cost effective graph (Figure 11).

computational-mathematics-cost-effective

Figure 11: C4W1,3 of the very cost effective.

2) Let G1 and G2 be the very cost effective graphs shown in Figure 12. Then the join graph G1G2 is also very cost effective graph (Figure 12).

computational-mathematics-effective-graph

Figure 12: G1G2 is also very cost effective graph.

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 G1=(V1, E1), G2=(V2, E2), G3=(V3, E3) and G4=(V4, E4) be graphs. Let f: G1G3 and g: G2G4 be graph maps. A join map fV g: G1V G2G3V G4 is a map defined by

For each vertex

For each edge e=(v1,v2), v1 ∈ V1 and v2 ∈ v2, (f⋁ g){e}={f(v1),g(v2)} ∈ G3G4.

If e=(u1, v1)∈E1, then (f ⋁ g){e}={f(u1), f(v1)}, also if e=(u2, v2)∈E2, then (f ⋁ g){e}=(f ⋁ g){(u2, v2)}={ g(u2), g(v2)} [3].

Definition (3.2)

A graph folding f: G1→G2 between two graphs G1 and G2 is a very cost effective graph folding if the image f(G1)=H ⊆ G2 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 C4 where V(C4)={u1, u2, u3, u4} and E(C4)={e1, e2, e3, e4} then the graph folding f: C4→C4 defined by f{u1, u2, u3, u4}={u3, u2, u3, u4} and f{e1, e2, e3, e4}={e4, e3, e3, e4} is a very cost effective graph folding since the image is P3 (Figure 13).

computational-mathematics-effective-graph

Figure 13: P3 is also very cost effective graph.

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)={v1, v2, v3, v4} and E(G)={e1, e2, e3, e4, e5} then the graph folding g: G→G defined by g{v1}={v3} and g{e1, e2}={e4, e3} is not a very cost effective.

computational-mathematics-effective-graph

Figure 14: G is not cost effective graph.

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 G1=P3 and G2=P4 as shown in Figure 15. Let f : G1→G1 and g: G2→G2 be the very cost effective graph foldings defined by f{v1}={v3}, f{e1}={e2} and g{u1, u4}={u3, u2} and g{e3, e5}={e4, e4}. The join graph folding f ∨g: G1⋁G2→G1⋁G2 defined by (f⋁g){u1, u4, v1}={u3, u2, v3} is a very cost effective graph folding.

computational-mathematics-effective-graph

Figure 15: f ∨g: G1∨ G2 → G1 ∨ G2 is a very cost effective graph.

Theorem (3.4)

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

Theorem (3.5)

Consider the wheel graphs W1,4 and W1,6 shown in Figure 16. Let f: W1,4→W1,4 and g: W1,6→W1,6 be the very cost effective graph folding defined By f{u1}={u3} and f{e1, e4, e5}={e2, e3, e7} and g{v1, v5, v6}={v3, v3, v4} and g{e1, e4, e5, e6, e7, e11, e12}={e2, e3, e4, e3, e9, e9, e10}. Then The join graph folding f ∨g: W1,4 ∨ W1,6→W1,4 ∨ W1,6 is a very cost effective graph folding (Figure 16).

computational-mathematics-effective-graph

Figure 16: f ∨g: W1,4 ∨ W1,6 → W1,4 ∨ W1,6 is a very cost effective graph.

References

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.

Select your language of interest to view the total content in your interested language

Post Your Comment Citation
Share This Article
Article Usage
  • Total views: 915
  • [From(publication date): 0-2018 - Dec 11, 2018]
  • Breakdown by view type
  • HTML page views: 860
  • PDF downloads: 55

Post your comment

captcha   Reload  Can't read the image? click here to refresh