Abstract
Let G be an eulerian digraph; let ν(G) be the maximum number of pairwise edge-disjoint directed circuits of G, and τ(G) the smallest size of a set of edges that meets all directed circuits of G. Borobia, Nutov and Penn showed that ν(G) need not be equal to τ(G). We show that ν(G) = τ(G) provided that G has a "linkless" embedding in 3-space, or equivalently, if no minor of G can be converted to K6 by Δ - Y and Y - Δ operations.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 223-231 |
| Number of pages | 9 |
| Journal | Combinatorica |
| Volume | 16 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1996 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics