Conjecture on non-Hamiltonian graphs with an arbitrarily high fraction of Hamiltonian vertex pairs
Statement
Let be a graph, and let denote the fraction of pairs of vertices of that are connected by a Hamiltonian path. Equivalently, if has order , define
where is -pair strung when pairs of vertices can be connected by a Hamiltonian path. The conjecture. For every , there exists a graph such that
The conjecture predicts graphs in which an arbitrarily large fraction of vertex pairs are connected by Hamiltonian paths, despite the broader discussion concerning non-Hamiltonian graphs. The paper describes constructions whose corresponding fractions approach and ; finding graphs with arbitrarily large H-path connected edge sets would establish the stated bound.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.