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
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      19 April 2005
      0 references
      Hamilton cycles
      0 references
      graph linkages
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references