Skip to Main content Skip to Navigation

(d,1)-total labelling of graphs

Frédéric Havet 1 Min-Li Yu
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 : A $(d,1)$-total labelling of a graph $G$ is an assignment of integers to $V(G)\cup 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) a vertex and its incident edge receive integers that differ by at least $d$ in absolute value. The {\it span} of a $(d,1)$-total labelling is the maximum difference between two labels. The minimum span of a $(d,1)$-total labelling of $G$ is denoted by $\lambda_d^T(G)$. We show $\lambda_d^T\leq 2\D d -1$ and conjecture $\lambda_d^T\leq \D2d -1$, where $\Dis the maximum degree of a vertex in a graph. We prove this conjecture for complete graphs. More precisely, we determine the exact value of $\lambda_d(K_n)$ except for even $n$ in the interval $[d+5, 6d^2-10d+4]$ for which we show that $\lambda_d^T(K_n) \in \{n+2d-3, n+2d-2\}$. We then give some evidences for the conjecture to be true. We prove it when $\Dleq 3$. We also show that as $n=|G|\rightarrow \infty$, $\lambda_d^T\leq \D O(\log n/ \log \log n)$ and the proportion of graphs on vertices $1,2,\dots ,n$ with $\lambda_d^T> \D2d-1$ is very small. Finally, we show that any vertex colouring may be extended to a fractional $(d,1)$-total labelling with span at most $\D 3d$.
Document type :
Complete list of metadata

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


  • HAL Id : inria-00071935, version 1



Frédéric Havet, Min-Li Yu. (d,1)-total labelling of graphs. RR-4650, INRIA. 2002. ⟨inria-00071935⟩



Record views


Files downloads