zbMATH — the first resource for mathematics

Packing directed circuits fractionally. (English) Zbl 0826.05031
A fractional circuit packing of value \(v\) of a directed graph \(G\) is a function that assigns a non-negative rational number \(q(C)\) to each circuit \(C\) such that (i) the sum of \(q(C)\) over all circuits containing any given vertex is at most one, and (ii) the sum of \(q(C)\) over all circuits is \(v\). The author shows that if every fractional circuit packing of \(G\) has value at most \(k\) where \(k\geq 1\), then there exists a set of at most \(4k\log(4k) \log\log_2(4k)\) vertices of \(G\) that meets every circuit.

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] N. Alon, andJ. H. Spencer:The Probabilistic Method, Wiley, 1991.
[2] A. Lubotzky, R. Phillips, andP. Sarnak: Ramanujan graphs,Combinatorica 8 (1988), 261-277. · Zbl 0661.05035 · doi:10.1007/BF02126799
[3] G. A. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators,Problemy Pederachi Informatsii 24 (1988), 51-60 (in Russian). English translation inProblems of Information Transmission 24 (1988), 39-46.
[4] W. McCuaig: Intercyclic digraphs,Graph Structure Theory (Neil Robertson and Paul Seymour, eds.), AMS Contemporary Math., (147) 1991, 203-245.
[5] D. H. Younger: Graphs with interlinked directed circuits,Proceedings of the Midwest Symposium on Circuit Theory 2 (1973), XVI 2.1-XVI 2.7.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.