Hamilton path conjecture for connected graphs with exactly two spanning paths after vertex deletion

Let GG be a connected graph on n2n\geq 2 vertices. Here, ψk(G)\psi_k(G) denotes the number of paths in GG with kk vertices.

Hamilton path conjecture. The following implication holds

ψn1(G)=2ψn(G)=1.\psi_{n-1}(G)=2 \Rightarrow \psi_n(G)=1.

The conjecture asserts that a connected graph with exactly two paths on n1n-1 vertices must contain a Hamilton path. It was proposed from computational data for graphs with up to nine vertices, and the source states that, to the authors' knowledge, it had not previously been studied.

Sources & referencesView supporting material

Primary source

Sławomir Bakalarski and Jakub Zygadło, “On path sequences of graphs”, arXiv:1511.05384 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.