Premium
On minimum degree in Hamiltonian path graphs
Author(s) -
Hendry George R. T.
Publication year - 1988
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.3190120404
Subject(s) - mathematics , combinatorics , hamiltonian path , graph , degree (music) , discrete mathematics , path (computing) , physics , acoustics , computer science , programming language
For integers p and s satisfying 2 ⩽ s ⩽ p − 1, let m ( p,s ) denote the maximum number of edges in a graph G of order p such that the minimum degree in the hamiltonian path graph of G equals s . The values of m ( p, s ) are determined for 2 ⩽ s ⩽ p/2 and for (2 p − 2)/3 ⩽ s ⩽ p − 1, and upper and lower bounds on m ( p, s ) are obtained for p /2 < s < (2 p − 2)/3.