Premium
Sufficient Conditions for Circuits in Graphs †
Author(s) -
Woodall D. R.
Publication year - 1972
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-24.4.739
Subject(s) - mathematics , valency , combinatorics , hamiltonian path , pancyclic graph , discrete mathematics , undirected graph , graph , directed graph , graph power , line graph , 1 planar graph , philosophy , linguistics
Certain lower bounds on the valencies of the vertices in a graph, and/or on the total number of edges, suffice to ensure the existence in the graph of a circuit of at least, or exactly, a certain specified length. Many theorems of this type are listed, some old and some new. The culminating result on undirected graphs shows how many edges are needed in a graph on n vertices, with minimal valency at least k , in order to ensure the existence of a circuit of length exactly n − r . (Erdös mentioned the case k = 0, as an unsolved problem, in 1969: see [5].) A few of these results have been extended to directed graphs. The main extension proved here is that if G is a directed graph on n vertices, in which ρ out (a) + ρ in (b) ⩾ n for every pair of distinct vertices a and b such that a is not joined to b (by an edge of G ), then G has a (directed) Hamiltonian circuit.