Label-connected graphs and the gossip problem (Q804593)

A graph G is called label-connected if the edges of G can be labeled by real numbers so that for every pair (u,v) of vertices of G there is an (u,v)-path with ascending labels. It is shown (using the gossip problem) that the minimum number of edges of a label-connected graph on n vertices is 2n-4. A necessary and sufficient condition for a graph to be label-connected is given. It is proved that recognizing label-connected graphs is NP-complete.