Szczegóły publikacji
Opis bibliograficzny
On the set of cycle lengths in a hamiltonian graph with a given maximum degree / Antoni MARCZYK // Graphs and Combinatorics ; ISSN 0911-0119. — 2004 — vol. 20 iss. 4, s. 517–529. — Bibliogr. s. 529, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 19252 |
|---|---|
| Data dodania do BaDAP | 2005-01-26 |
| Tekst źródłowy | URL |
| DOI | 10.1007/s00373-004-0580-1 |
| Rok publikacji | 2004 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Graphs and Combinatorics |
Abstract
Let n and Delta be two integers such that 2 less than or equal to Delta less than or equal to n - 1. We describe the set of cycle lengths occurring in any hamiltonian graph G of order n and maximum degree Delta. We conclude that for the case n/2 < &UDelta; &LE; 2n-2/3 this set contains all the integers belonging to the union [3, 2&UDelta; - n + 2] &OR;[n -&UDelta; + 2; &UDelta;+1], and for 2n-2/3 < Delta less than or equal to n - 1 it contains every integer between 3 and Delta+1. We also study the set of cycle lengths in a hamiltonian graph with two fixed vertices of large degree sum. Our main results imply that the stability s(P) for the property of being pancyclic satisfies s(P) less than or equal to [4n/3] + 8/3.
