On Independent Circuits Contained in a Graph 论文

摘要

A family of circuits of a graph G is said to be independent if no two of the circuits have a common vertex; it is called edge-independent if no two of them have an edge in common. A set of vertices will be called a representing set for the circuits (for the sake of brevity we shall call it a representing set), if every circuit of G passes through at least one vertex of the representing set. Denote by I ( G ) = k the maximum number of circuits in an independent family and by R ( G ) the minimum number of vertices of a representing set. Dirac and Gallai asked whether there is any relation between I ( G ) and R ( G ) (trivially R ( G ) ≥ I ( G )).