# Label-connected graphs and the gossip problem

Göbel, F. and Orestes Cerdeira, J. and Veldman, H.J. (1991) *Label-connected graphs and the gossip problem.* Discrete Mathematics, 87 (1). pp. 29-40. ISSN 0012-365X

| PDF 790Kb |

Abstract: | 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 ≥ 4. A polynomial characterization of label-connected graphs with n vertices and 2n − 4 edges is obtained. For a graph G, let θ(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) ≤ 2 is necessary and θ(G) ≤ 1 is sufficient. For i = 1, 2, the condition θ(G) ≤ 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? |

Item Type: | Article |

Copyright: | © 1991 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/72986 |

Official URL: | http://dx.doi.org/10.1016/0012-365X(91)90068-D |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 140352