Premium
On the hamiltonian path graph of a graph
Author(s) -
Hendry George R. T.
Publication year - 1987
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.3190110312
Subject(s) - combinatorics , mathematics , hamiltonian path , factor critical graph , discrete mathematics , graph power , quartic graph , graph , induced path , vertex (graph theory) , line graph
The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u − v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K̄ d ⊆ H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least | V(F) | + t(t ⩾ 0), then H(F) contains a complete subgraph of order t + 4.