Ben Seamone ; Brett Stevens - Sequence variations of the 1-2-3 conjecture and irregularity strength

dmtcs:635 - Discrete Mathematics & Theoretical Computer Science, January 28, 2013, Vol. 15 no. 1 -
Sequence variations of the 1-2-3 conjecture and irregularity strengthArticle

Authors: Ben Seamone ORCID1; Brett Stevens 1

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.

Volume: Vol. 15 no. 1
Section: Graph Theory
Published on: January 28, 2013
Accepted on: June 9, 2015
Submitted on: March 23, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

3 Documents citing this article

Consultation statistics

This page has been seen 487 times.
This article's PDF has been downloaded 320 times.