Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
Abstrak
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 weights 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 $\mathcal{S}$-edge-weighting for $\mathcal{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 $\mathcal{S}$-edge-weighting for $\mathcal{S} \in \{ \{ 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 $\mathcal{S}$-edge-weightings for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$.
Topik & Kata Kunci
Penulis (1)
Hongliang Lu
Akses Cepat
- Tahun Terbit
- 2016
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.2162
- Akses
- Open Access ✓