On mutually independent Hamiltonian paths (Q2488717): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Hamilton's ideals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On maximal paths and circuits of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mutually independent hamiltonian paths in star networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamilton connected graphs / rank | |||
Normal rank |
Latest revision as of 13:57, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On mutually independent Hamiltonian paths |
scientific article |
Statements
On mutually independent Hamiltonian paths (English)
0 references
11 May 2006
0 references
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.
0 references
Hamiltonian connected
0 references