Linear forests and ordered cycles (Q4668422)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2158873
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Linear forests and ordered cycles |
scientific article; zbMATH DE number 2158873 |
Statements
Linear forests and ordered cycles (English)
0 references
19 April 2005
0 references
Hamilton cycles
0 references
graph linkages
0 references
0.9446287155151368
0 references
0.8358122110366821
0 references
0.834499180316925
0 references
0.8004046678543091
0 references
A \((k,t,s)\)-linear forest \(L\) in a graph \(G\) is a collection of \(t\) disjoint paths, \(s\) of them being singletons and with \(| V(L)| =k\). A graph \(G\) is strongly \((k,t,s)\)-ordered Hamiltonian if for every \((k,t,s)\)-linear forest \(L\) for which each path is oriented, there exists a Hamiltonian path \(C\) in \(G\) that encounters the paths in \(L\) in the designated order and orientation. The main result is: if \(0\leq s\leq t \leq k\), and \(G\) is a graph of order \(n\geq \max\{178t+k,8t^2+k\}\) with \[ \sigma_2(G) \geq \begin{cases} n+k-3 &\text{if }s=0, \;t\geq3 \\ n+k+s-4 &\text{if } 0<2s\leq t,\;t\geq 3 \\ n+k+\frac{t-9}{2} &\text{if }2s>t\geq 3 \\ n+k-2 &\text{if }s\leq 1,\;t=2 \\ n+k-1 &\text{if }s=0, \;t=1 \\ n &\text{if }s=t\leq 2 \end{cases} \] then \(G\) is strongly \((k,t,s)\)-ordered Hamiltonian (here \(\sigma_2(G)\) is the minimum degree sum of two nonadjacent vertices in \(G\)).
0 references