Please use this identifier to cite or link to this item:
https://gnanaganga.inflibnet.ac.in:8443/jspui/handle/123456789/7614
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Todd Thomas | - |
dc.contributor.author | Gary Chartrand | - |
dc.date.accessioned | 2024-02-27T06:20:32Z | - |
dc.date.available | 2024-02-27T06:20:32Z | - |
dc.date.issued | 2004 | - |
dc.identifier.uri | http://gnanaganga.inflibnet.ac.in:8080/jspui/handle/123456789/7614 | - |
dc.description.abstract | Let G be a connected graph of order n. A Hamiltonian walk of G is a closed spanning walk of minimum length in G. For a cyclic ordering s : v1, v2 , • • , vn , = v1 of V (G), let d(s) = ∑n i= 1 d(vi, vi+ 1 ), where d(vi, vi+1) is the distance between vi and vi+.1 for 1 < i < n. Then the Hamiltonian number h(G) of G is defined as h(G) = min {d(s)} , where the minimum is taken over all cyclic orderings s of V(G). It is shown that h(G) is the length of a Hamiltonian walk in G. Thus h(G) = n if and only if G is a Hamiltonian graph. It is also shown that h(G) = 2n — 2 if and only if G is a tree. Moreover, for every pair n, k of integers with 3 < n < k < 2n — 2, there exists a connected graph G of order n having h(G) = k. The upper Hamiltonian number is defined as h+ (G) = max {d(s)} , where the maximum is taken over all cyclic orderings s of V(G). We show, for a connected graph G of order II > 3, that h(G) = (G) if and only if G = Kn or G = K11,1. We also study the upper Hamiltonian number of a tree and present bounds for the upper Hamiltonian number of a connected graph in terms of its order. | - |
dc.publisher | Bulletin of the Institute of Combinatorics and Its Applications | - |
dc.title | A New Look at Hamiltonian Walks | - |
dc.vol | Vol 42 | - |
Appears in Collections: | Articles to be qced |
Files in This Item:
File | Size | Format | |
---|---|---|---|
A New Look at Hamiltonian Walks.pdf Restricted Access | 3.52 MB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.