Packing directed circuits fractionally.

*(English)*Zbl 0826.05031A 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.

Reviewer: J.W.Moon (Edmonton)

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

05C38 | Paths and cycles |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

PDF
BibTeX
XML
Cite

\textit{P. D. Seymour}, Combinatorica 15, No. 2, 281--288 (1995; Zbl 0826.05031)

Full Text:
DOI

##### References:

[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.