Skip to Main content Skip to Navigation

Upper bound for the span of (s,1)-total labelling of graphs

Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An (s,1)-total labelling of a graph G is an assignment of integers to V(G)E(G) such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) incident vertex and edge receive integers that differ by at least s in absolute value. The span of a (s,1)-total labelling is the maximum difference between two labels. The minimum span of a (s,1)-total labelling of G is denoted by _s^T(G). In , it is conjectured that _s^T+ 2s -1, where is the maximum degree of a vertex in a graph. This is an extension of the Total Colouring Conjecture. It is also shown that _s^T2+ s -1 and _2^T(G)6 if (G)3 and _2^T(G)8 if (G)4. In this paper, we prove that _s^T2-(+2) + s -1 +2(16s-10). The proof is an induction based on the maximal cut of a graph. We use the same technique to improve a little bit this result in the case of (2,1)-total labelling. We prove that if (G) 3, then _2^T(G)2(G) and that if (G)5 is odd then _2^T(G)2(G)-1.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:43:36 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:37:05 PM


  • HAL Id : inria-00071770, version 1



Frédéric Havet. Upper bound for the span of (s,1)-total labelling of graphs. RR-4816, INRIA. 2003. ⟨inria-00071770⟩



Record views


Files downloads