Premium
Counterexamples to faudree and schelp's conjecture on hamiltonian‐connected graphs
Author(s) -
Thomassen Carsten
Publication year - 1978
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.3190020409
Subject(s) - combinatorics , mathematics , counterexample , conjecture , hamiltonian path , hamiltonian (control theory) , path (computing) , graph , discrete mathematics , computer science , mathematical optimization , programming language
Faudree and Schelp conjectured that for any two vertices x, y in a Hamiltonian‐connected graph G and for any integer k , where n /2 ⩽ k ⩽ n − 1, G has a path of length k connecting x and y . However, we show in this paper that there are infinitely many exceptions to this conjecture and we comment on some problems on path length distribution raised by Faudree and Schelp.