Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

Hongliang Lu

Abstract


Let G be a graph and S be a subset of Z. A vertex-coloring S-edge-weighting of G is an assignment of weights by the elements of S to each edge of G so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring S-edge-weighting for S={1,2} (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring S-edge-weighting for S∈ {{0,1},{1,2}}. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring S-edge-weightings for S∈{{0,1},{1,2}}.

Full Text: PDF