Linear forests and ordered cycles

Guantao Chen; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak; Florian Pfender

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 359-372
  • ISSN: 2083-5892

Abstract

top
A collection L = P ¹ P ² . . . P t (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.

How to cite

top

Guantao Chen, et al. "Linear forests and ordered cycles." Discussiones Mathematicae Graph Theory 24.3 (2004): 359-372. <http://eudml.org/doc/270240>.

@article{GuantaoChen2004,
abstract = {A collection $L = P¹ ∪ P² ∪ ... ∪ P^t$ (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.},
author = {Guantao Chen, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Linda Lesniak, Florian Pfender},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamilton cycles; graph linkages; Hamilton cycles},
language = {eng},
number = {3},
pages = {359-372},
title = {Linear forests and ordered cycles},
url = {http://eudml.org/doc/270240},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Guantao Chen
AU - Ralph J. Faudree
AU - Ronald J. Gould
AU - Michael S. Jacobson
AU - Linda Lesniak
AU - Florian Pfender
TI - Linear forests and ordered cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 359
EP - 372
AB - A collection $L = P¹ ∪ P² ∪ ... ∪ P^t$ (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.
LA - eng
KW - hamilton cycles; graph linkages; Hamilton cycles
UR - http://eudml.org/doc/270240
ER -

References

top
  1. [1] B. Bollobás and A. Thomason, Highly Linked Graphs, Combinatorics, Probability, and Computing, (1993) 1-7. 
  2. [2] J.R. Faudree, R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, On k-Ordered Graphs, J. Graph Theory 35 (2000) 69-82, doi: 10.1002/1097-0118(200010)35:2<69::AID-JGT1>3.0.CO;2-I Zbl0958.05083
  3. [3] R.J. Faudree, R.J., Gould, A. Kostochka, L. Lesniak, I. Schiermeyer and A. Saito, Degree Conditions for k-ordered hamiltonian graphs, J. Graph Theory 42 (2003) 199-210, doi: 10.1002/jgt.10084. Zbl1014.05045
  4. [4] Z. Hu, F. Tian and B. Wei, Long cycles through a linear forest, J. Combin. Theory (B) 82 (2001) 67-80, doi: 10.1006/jctb.2000.2022. Zbl1026.05065
  5. [5] H. Kierstead, G. Sarkozy and S. Selkow, On k-Ordered Hamiltonian Graphs, J. Graph Theory 32 (1999) 17-25, doi: 10.1002/(SICI)1097-0118(199909)32:1<17::AID-JGT2>3.0.CO;2-G Zbl0929.05055
  6. [6] W. Mader, Existenz von n-fach zusammenhängenden Teilgraphen in Graphen genügend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972) 86-97, doi: 10.1007/BF02993903. Zbl0215.33803
  7. [7] L. Ng and M. Schultz, k-Ordered Hamiltonian Graphs, J. Graph Theory 24 (1997) 45-57, doi: 10.1002/(SICI)1097-0118(199701)24:1<45::AID-JGT6>3.0.CO;2-J 
  8. [8] R. Thomas and P. Wollan, An Improved Edge Bound for Graph Linkages, preprint. Zbl1056.05091

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.