HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:43:36 PM
Last modification on : Friday, February 4, 2022 - 3:11:42 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