Label-connected graphs and the gossip problem (Q804593): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:16, 5 March 2024
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