On Independent Circuits Contained in a Graph

Publisher Website
Google Scholar
Abstract
A family of circuits of a graphGis said to beindependentif no two of the circuits have a common vertex; it is callededge-independentif no two of them have an edge in common. A set of vertices will be called arepresentingset for the circuits (for the sake of brevity we shall call it a representing set), if every circuit ofGpasses through at least one vertex of the representing set. Denote byI(G) =kthe maximum number of circuits in an independent family and byR(G) the minimum number of vertices of a representing set. Dirac and Gallai asked whether there is any relation betweenI(G) andR(G) (triviallyR(G) ≥I(G)).

This publication has 4 references indexed in Scilit: