{"id":"arxiv/2606.02279","url":"https://arxiv.org/abs/2606.02279","tags":["math.CO"],"score":0,"title":"Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph","domain":"math.CO","source":"arxiv","authors":["Jorik Jooken","Carol T. Zamfirescu"],"reviews":0,"subject":"math.CO","summary":"For graphs $G$ and $F$, we say that $G$ is $F$-free if $F$ does not occur as an induced subgraph of $G$. This paper is concerned with the following question: Given an $F$-free graph $G$ having two vertices between which there exists at least one Hamiltonian path, how many Hamiltonian paths between these endpoints must exist (in terms of the order of $G$)? Our main result shows that there exists a sharp dichotomy. More precisely, we show that if $F$ is not an induced subgraph of $P_3+sP_1$ for any integer $s \\geq 0$, then there exists an infinite family of $F$-free graphs having two vertices…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-01","reactions":{}}