(d,1)-total labelling of graphs
Résumé
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$.
Domaines
Autre [cs.OH]
Loading...