Sequence variations of the 1-2-3 conjecture and irregularity strength

Abstract : Karonski, Luczak, and Thomason (2004) conjecture that, for any connected graph G on at least three vertices, there exists an edge weighting from 1, 2, 3 such that adjacent vertices receive different sums of incident edge weights. Bartnicki, Grytczuk, and Niwcyk (2009) make a stronger conjecture, that each edge's weight may be chosen from an arbitrary list of size 3 rather than 1, 2, 3. We examine a variation of these conjectures, where each vertex is coloured with a sequence of edge weights. Such a colouring relies on an ordering of E(G), and so two variations arise - one where we may choose any ordering of E(G) and one where the ordering is fixed. In the former case, we bound the list size required for any graph. In the latter, we obtain a bound on list sizes for graphs with sufficiently large minimum degree. We also extend our methods to a list variation of irregularity strength, where each vertex receives a distinct sequence of edge weights.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.15--28
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990603
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:28:44
Dernière modification le : jeudi 7 septembre 2017 - 01:03:47
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:45:41

Fichier

2123-7662-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990603, version 1

Collections

Citation

Ben Seamone, Brett Stevens. Sequence variations of the 1-2-3 conjecture and irregularity strength. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.15--28. 〈hal-00990603〉

Partager

Métriques

Consultations de la notice

208

Téléchargements de fichiers

139