
arXiv: 1205.3266
Graph Theory 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.
Edge weighting, vertex-coloring edge-weighting, Vertex-coloring 2-edge-weighting, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], vertex-coloring 2-edge-weighting, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 05C15, QA1-939, FOS: Mathematics, Vertex-coloring edge-weighting, Mathematics - Combinatorics, edge weighting, Combinatorics (math.CO), 1-2-3-conjecture, [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics
Edge weighting, vertex-coloring edge-weighting, Vertex-coloring 2-edge-weighting, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], vertex-coloring 2-edge-weighting, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 05C15, QA1-939, FOS: Mathematics, Vertex-coloring edge-weighting, Mathematics - Combinatorics, edge weighting, Combinatorics (math.CO), 1-2-3-conjecture, [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
