Annals of the New York Academy of Sciences · 1979 · 18 citations · 0 references
Natural SciencesMathematicsCombinatoricsComputational GeometryDiscrete MathematicsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryHamiltonian GraphsHamiltonian Path AlgorithmsHamiltonian Path ProblemHamiltonian Paths
S ummary A graph G is homogeneously traceable if for every vertex v of G there exists a hamiltonian path with initial vertex v. It is shown that there exists a homogeneously traceable nonhamiltonian graph of order p , for all positive integers p except for 3 ≤ p ≤ 8. Further, if G is a homogeneously traceable nonhamiltonian graph of order p , then {5 p /4} is a sharp lower bound on the size of G and the maximum degree of G is at most p – 4 for p ≥ 9.