1972/05/01 by D. R. Woodall, Douglas R. Woodall · 7 citations
Engineering · Computer Science · #graph theory and CDMA systems #Advanced Graph Theory Research #VLSI and FPGA Design Techniques
paper · doi:10.1112/plms/s3-24.4.739
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.