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

Let $G$ be a graph and $\mathcal {S}$ be a subset of $Z$. A vertex-coloring $\mathcal {S}$-edge-weighting of $G$ is an assignment of weight $s$ by the elements of $\mathcal {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 $\{1,2\}$-edge-weighting (Lu, Yu and Zhang, (2011) \cite{LYZ}). In this paper, we show that the following result: if a 3-edge-connected bipartite graph $G$ with minimum degree $δ$ contains a vertex $u\in V(G)$ such that $d_G(u)=δ$ and $G-u$ is connected, then $G$ admits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. In particular, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. The bound is sharp, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\{1,2\}$-edge-weightings or vertex-coloring $\{0,1\}$-edge-weightings.

No reviews yet.

No comments yet.