Label-connected graphs and the gossip problem (Q804593): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Problem with Telephones / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The communication problem on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Further gossip problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3048571 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge-Disjoint Spanning Trees of Finite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Problem of Decomposing a Graph into <i>n</i> Connected Factors / rank | |||
Normal rank |
Latest revision as of 17:16, 21 June 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