2012/05/15 by Davoodi, Akbar, Omoomi, Behnaz
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1205.3266
A k-edge-weighting of a graph G is a function w: E(G)->1,2,...,k. An edge-weighting naturally induces a vertex coloring c, where for every vertex v in V(G), c(v) is sum of weights of the edges that are adjacent to vertex v. If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge weighting (VCk-EW). Karonski et al. (J. Combin. Theory Ser. B 91 (2004) 151-157) conjectured that every graph admits a VC3-EW. This conjecture is known as 1-2-3-conjecture. In this paper, frst, we study the vertex-coloring edge-weighting of the cartesian product of graphs. Among some results, we prove that the 1-2-3-conjecture holds for some infinite classes of graphs. Moreover, we explore some properties of a graph to admit a VC2-EW