Labelconnected graphs and the gossip problem
Göbel, F. and Orestes Cerdeira, J. and Veldman, H.J. (1991) Labelconnected graphs and the gossip problem. Discrete Mathematics, 87 (1). pp. 2940. ISSN 0012365X

PDF
809kB 
Abstract:  A graph with m edges is called labelconnected 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 labelconnected 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 labelconnected 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 edgedisjoint spanning trees. It is shown that for a graph G to be labelconnected, θ(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 labelconnected graphs is an NPcomplete problem. This is established by first showing that the following problem is NPcomplete: 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/0012365X(91)90068D 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140352