Packing circuits in Eulerian digraphs

Research output: Contribution to journalArticle

18 Scopus citations

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 languageEnglish (US)
Pages (from-to)223-231
Number of pages9
JournalCombinatorica
Volume16
Issue number2
DOIs
StatePublished - Jan 1 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Packing circuits in Eulerian digraphs'. Together they form a unique fingerprint.

  • Cite this