On the maximum density of graphs with unique-path labellings

Description

A unique-path labelling of a simple, fi nite graph is a labelling of its edges with real numbers such that, for every ordered pair of vertices (u,v), there is at most one nondecreasing path from u to v. In this paper we prove that any graph on n vertices that admits a unique-path labelling has at most n log_2(n)/2 edges, and that this bound is tight for in finitely many values of n. Thus we signi cantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every n we also construct an n-vertex graph that admits a unique-path labelling and has n log2(n)/2 - O(n) edges.

Abstract

International audience

Additional details