Szczegóły publikacji
Opis bibliograficzny
Sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles / Zdzisław SKUPIEŃ // Discrete Mathematics ; ISSN 0012-365X . — 2009 — vol. 309 iss. 22, s. 6382–6390. — Bibliogr. s. 6390, Abstr. — Fifth Cracow Conference on Graph Theory “Ustron 2006” : Ustroń, September 11 to 15, 2006
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 48383 |
|---|---|
| Data dodania do BaDAP | 2009-11-12 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2008.11.003 |
| Rok publikacji | 2009 |
| Typ publikacji | referat w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
We construct multigraphs of any large order with as few as only four 2-decompositions into Hamilton cycles or only two 2-decompositions into Hamilton paths. Nevertheless, some of those multigraphs are proved to have exponentially many Hamilton cycles (Hamilton paths). Two families of large simple graphs are constructed. Members in one class have exactly 16 hamiltonian pairs and in another class exactly four traceable pairs. These graphs also have exponentially many Hamilton cycles and Hamilton paths, respectively. The exact numbers of (Hamilton) cycles and paths are expressed in terms of Lucas- or Fibonacci-like numbers which count 2-independent vertex (or edge) subsets on the n-path or n-cycle. A closed formula which counts Hamilton cycles in the square of the n-cycle is found for n ≥ 5. The presented results complement, improve on, or extend the corresponding well-known Thomason's results. © 2008 Elsevier B.V. All rights reserved.
