Label-connected graphs and the gossip problem (Q804593)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Label-connected graphs and the gossip problem |
scientific article |
Statements
Label-connected graphs and the gossip problem (English)
0 references
1991
0 references
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.
0 references
label-connected graph
0 references