Cycle Lengths of Hamiltonian $$P_\ell $$ P ℓ -free Graphs

Autor: Dirk Meierling, Dieter Rautenbach
Rok vydání: 2014
Předmět:
Zdroj: Graphs and Combinatorics. 31:2335-2345
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-014-1494-1
Popis: For an integer $$\ell $$l at least three, we prove that every Hamiltonian $$P_\ell $$Pl-free graph $$G$$G on $$n>\ell $$n>l vertices has cycles of at least $$\frac{2}{\ell }n-1$$2ln-1 different lengths. For small values of $$\ell $$l, we can improve the bound as follows. If $$4\le \ell \le 7$$4≤l≤7, then $$G$$G has cycles of at least $$\frac{1}{2}n-1$$12n-1 different lengths, and if $$\ell $$l is $$4$$4 or $$5$$5 and $$n$$n is odd, then $$G$$G has cycles of at least $$n-\ell +2$$n-l+2 different lengths.
Databáze: OpenAIRE
Externí odkaz: