应用与计算数学杂志

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

Abstract

El-Kholy EM1

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.