# (d,1)-total labelling of graphs

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\$.
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00071935
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

### Identifiers

• HAL Id : inria-00071935, version 1

### Citation

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

Record views