Some Results on Vertex Coloring Edge Weighting of Double Graphs and Join Graphs

Abstract

The edge weighting problem of graphs has interesting real life applications in the optimization and the network design, such as the file transfers in computer networks. A k-edge weighting of a graph G is a mapping w : E(G)®{1,, k}. An edge-weighting w induces a vertex coloring f (v) w given by Î = e v f (v) w(e) w for each v ÎV(G) . An edge weighting w is vertex coloring if ( ) ( ) f u f v w w ¹ for each edge uvÎ E(G) . The current paper studies the parameter (G) e c , which is the minimum k for which G has a vertex coloring k-edge weighting. Exact value of (G) e c are determined for several double graph and join graph of some graphs.