A Degree Constraint for Uniquely Hamiltonian Graphs |
| |
| Authors: | Sarmad Abbasi Asif Jamshed |
| |
| Affiliation: | (1) Department of Computer Science, National University of Computer & Emerging Sciences, Lahore, Pakistan;(2) Department of Computer Science, Lahore University of Management Sciences, Lahore, Pakistan |
| |
| Abstract: | A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then  Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log2n+2 where c=(log23−1)−1≈1.71 thereby improving a bound given by Bondy and Jackson [3]. |
| |
| Keywords: | Hamilton Cycles Uniquely Hamiltonian graphs the probabilistic method |
| 本文献已被 SpringerLink 等数据库收录！ |
|
