On mutually independent Hamiltonian paths (Q2488717): Difference between revisions

Two Hamiltonian paths \(P_1=\langle v_1,v_2,\dots,v_n\rangle\) and \(P_2=\langle u_1,u_2,\dots,u_n\rangle\) of an \(n\)-vertex graph \(G\) are independent if \(u_1=v_1\), \(u_n=v_n\), and \(u_i\neq v_i\) for \(1<i<n\). A set of Hamiltonian paths \(P_1,P_2,\dots,P_s\) of \(G\) between two distinct vertices are mutually independent if any two distinct paths in the set are independent. Let \(\bar{e}\) denote the number of edges of the complement of \(G\). Suppose that \(G\) is a graph with \(\bar{e}\leq n-4\), \(n\geq4\). The authors prove that there are at least \(n-2-\bar{e}\) mutually independent Hamiltonian paths between any pair of distinct vertices of \(G\) except for \(n=5\) and \(\bar{e}=1\). Moreover, if the degree sum of any two non-adjacent vertices in \(G\) is at least \(n+2\) then for any two distinct vertices \(u\) and \(v\) of \(G\) there are \(\deg(u)+\deg(n)-n\) mutually independent paths between \(u\) and \(v\) if \(\{u,v\}\in E(G)\) and there are \(\deg(u)+\deg(v)-n+2\) mutually independent Hamiltonian paths between \(u\) and \(v\) otherwise.