Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T15:47:38.698Z Has data issue: false hasContentIssue false
  • English
  • Français

On Independent Circuits Contained in a Graph

Published online by Cambridge University Press:  20 November 2018

p. Erdös  and
L. Pósa
p. Erdös
Affiliation:
University of British Columbia, Vancouver, and Budapest, Hungary
L. Pósa
Affiliation:
University of British Columbia, Vancouver, and Budapest, Hungary
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 17 , 1965 , pp. 347 - 352
Copyright
Copyright © Canadian Mathematical Society 1965

References

1. Erdös, P. and Posa, L., On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen, 9 (1962), 3–12.Google Scholar
2. Erdös, P., Graph theory and probability, Can. J. Math., 11 (1959), 34–8.Google Scholar
3. Erdös, P., On circuits and subgraphs of chromatic graphs, Mathematika, 9 (1962), 170–5.Google Scholar
4. Gallai, T., Maximum-minimum Sàtze and verallgemeinerte Faktoren von Graphen. Acta Math. Hung. Acad. Sci., 12 (1961), 131–73; cf. pp. 158 and 161.Google Scholar