Skip to Main content Skip to Navigation
Journal articles

On the 1-2-3-conjecture

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196861
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, September 10, 2015 - 3:17:24 PM
Last modification on : Thursday, December 28, 2017 - 11:32:02 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:02:36 AM

File

dmtcs-17-1-4.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01196861, version 1

Collections

Citation

Akbar Davoodi, Behnaz Omoomi. On the 1-2-3-conjecture. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.67--78. ⟨hal-01196861⟩

Share

Metrics

Record views

152

Files downloads

936