The hamiltonian number problem is a generalization of hamiltonian cycle problem in graph theory. It is well known that the hamiltonian cycle problem in graph theory is NP-complete [16]. So the hamiltonian number problem is also NP-complete. On the other hand, the hamiltonian number problem is the traveling salesman problem with each edge having weight 1.
A hamiltonian walk of a graph G is a closed spanning walk of minimum length. The length of a hamiltonian walk in G is called the hamiltonian number. For graphs, we give some bounds for hamiltonian numbers of graphs. First, we improve some results in [14] and give a necessary and sufficient condition for h(G) < e(G) where e(G) is the minimum length of a closed walk passing through all edges of G. Next, we prove that if two nonadjacent vertices u and v satisfying that deg(u)+deg(v) ≥ |G|, then h(G) = h(G + uv). This result generalizes a theorem of Bondy and Chv¡¬atal for the hamiltonian cycle. Finally, we show that if 0 ≤ k ≤ n − 2 and G is a 2-connected graph of order n satisfying deg(u) + deg(v) + deg(w) ≥ 3n−k−2 for every independent set {u, v,w} of three vertices in G, then h(G) ≤ n+k. It is a generalization of a Bondy¡¦s result.
For digraphs, we give some bounds for hamiltonian numbers of digraphs first. We prove that if a digraph D of order n is strongly connected, thenn ≤ h(D) ≤ ⌊(n+1)^2/4 ⌋. Next, we also present some digraphs of order n ≥ 5 which have hamiltonian number k for n ≤ k ≤ ⌊(n+1)^2/4 ⌋. Finally, we study hamiltonian numbers of M¡Lobius double loop networks. We introduce M¡Lobius double loop network and every strongly connected double loop network is isomorphic to some M¡Lobius double loop network. Next, we give an upper bound for the hamiltonian numbers of M¡Lobius double loop networks. Then, we find some necessary and sufficient conditions for M¡Lobius double loop networks MDL(d, m, ℓ) to have hamiltonian numbers dm, dm + 1 or dm + 2.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0124111-164137 |
| Date | 24 January 2011 |
| Creators | Chang, Ting-pang |
| Contributors | Tsai-Lien Wong, Sen-Peng Eu, Hong-Gwa Yeh, Gerard Jennhwa Chang, Xuding Zhu, Dah-Jyh Guan, Ko-Wei Lih, Li-Da Tong |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0124111-164137 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0022 seconds