Premium
Graphs with exactly one hamiltonian circuit
Author(s) -
Sheehan John
Publication year - 1977
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190010110
Subject(s) - mathematics , combinatorics , hamiltonian (control theory) , hamiltonian path , graph , discrete mathematics , existential quantification , integer (computer science) , computer science , mathematical optimization , programming language
Let h(n ) be the largest integer such that there exists a graph with n vertices having exactly one Hamiltonian circuit and exactly h(n ) edges. We prove that h(n ) = [ n 2 /4]+1 ( n ≧ 4) and discuss some related problems.