Name
Abstract | ||
|---|---|---|
For a connected graph G, let L(G) denote the maximum number of leaves in a spanning tree in G. The problem of computing L(G) is known to be NP-hard even for cubic graphs. We improve on Lorys and Zwozniak's result presenting a 5/3-approximation for this problem on cubic graphs. This result is a consequence of new lower and upper bounds for L(G) which are interesting on their own. We also show a lower bound for L(G) that holds for graphs with minimum degree at least 3. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77918-6_15 | WAOA |
Keywords | Field | DocType |
cubic graph,connected graph,maximum number,upper bound,minimum degree,lower bound,spanning tree | Discrete mathematics,Trémaux tree,Indifference graph,Combinatorics,Minimum degree spanning tree,Tree-depth,Chordal graph,Pathwidth,1-planar graph,Pancyclic graph,Mathematics | Conference |
Volume | ISSN | ISBN |
4927 | 0302-9743 | 3-540-77917-5 |
Citations | PageRank | References |
8 | 0.56 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José R. Correa | 1 | 565 | 46.87 |
| Cristina G. Fernandes | 2 | 260 | 29.98 |
| Martín Matamala | 3 | 158 | 21.63 |
| Yoshiko Wakabayashi | 4 | 268 | 31.75 |