On the 1-2-3-conjecture
Akbar Davoodi, Behnaz Omoomi
Abstract
A k-edge-weighting of a graph G is a
function w:E(G)→{1,…,k}. An
edge-weighting naturally induces a vertex coloring c,
where for every vertex v∈V(G),
c(v)=∑e∼vw(e). If the induced
coloring c is a proper vertex coloring, then
w is called a vertex-coloring
k-edge-weighting (VC k-EW). Karoński
et al. (J. Combin. Theory Ser. B, 91 (2004) 151 13;157)
conjectured that every graph admits a VC 3-EW. This
conjecture is known as the
1-2-3-conjecture. In this
paper, first, we study the vertex-coloring edge-weighting of the
Cartesian product of graphs. We prove that if the
1-2-3-conjecture holds for two
graphs G and H, then it also holds for
G□H. Also we prove that the Cartesian product of
connected bipartite graphs admits a VC 2-EW. Moreover, we
present several sufficient conditions for a graph to admit a VC
2-EW. Finally, we explore some bipartite graphs which do
not admit a VC 2-EW.
Full Text: PDF PostScript