Label-connected graphs and the gossip problem

✍ Scribed by F. Göbel; J.Orestes Cerdeira; H.J. Veldman

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 791 KB
• Volume: 87
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90068-d

✦ Synopsis

Gobel, F., J. Orestes Cerdeira and H.J. Veldman, Label-connected graphs and the gossip problem, Discrete Mathematics 87 (1991) 29-40.

A graph with m edges is called label-connected if the edges can be labeled with real numbers in such a way that, for every pair (u, v) of vertices, there is a (u, v)-path with ascending labels. The minimum number of edges of a label-connected graph on n vertices equals the minimum number of calls in the gossip problem for n persons, which is known to be 2n -4 for n z 4. A polynomial characterization of label-connected graphs with n vertices and 2n -4 edges is obtained.

For a graph G, let 4(G) denote the minimum number of edges that have to be added to E(G) in order to create a graph with two edge-disjoint spanning trees. It is shown that for a graph G to be label-connected, $(G) c 2 is necessary and @(G) & 1 is sufficient. For i = 1, 2, the condition #(G) c i can be checked in polynomial time. Yet recognizing label-connected graphs is an NP-complete problem. This is established by first showing that the following problem is NP-complete:

Given a graph G and two vertices u and v of G, does there exist a (u, v)-path P in G such that G -E(P) is connected?