Name
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 2 n − 4 for n ⩾ 4. A polynomial characterization of label-connected graphs with n vertices and 2 n − 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? |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0012-365X(91)90068-D | Discrete Mathematics |
Keywords | Field | DocType |
gossip problem,label-connected graph,polynomial time,np complete problem,spanning tree,connected graph | Pseudoforest,Wheel graph,Discrete mathematics,Graph toughness,Combinatorics,Graph power,Bound graph,Cycle graph,Mathematics,Path graph,Complement graph | Journal |
Volume | Issue | ISSN |
87 | 1 | Discrete Mathematics |
Citations | PageRank | References |
7 | 2.79 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Göbel | 1 | 7 | 2.79 |
| J. Orestes Cerdeira | 2 | 32 | 8.45 |
| H. J. Veldman | 3 | 262 | 44.44 |