1965/01/01 by P. Erdös, L. Pósa · 251 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems #Vertex (graph theory) #Mathematics #Combinatorics #Electronic circuit #Graph #Set (abstract data type) #Discrete mathematics #Computer science
paper · pdf · doi:10.4153/cjm-1965-035-8
published in Canadian Journal of Mathematics 17, 347-352 (Cambridge University Press)
openalex publication_date 1965/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 )).