Semester

Summer

Date of Graduation

2005

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

Elaine M. Eschen.

Abstract

In modeling communication networks by graphs, the problem of designing s-fault-tolerant networks becomes the search for s-Hamiltonian graphs. This thesis is a study of the s-Hamiltonian index of a graph G.;A path P of G is called an arc in G if all the internal vertices of P are divalent vertices of G. We define l (G) = max{lcub}m : G has an arc of length m that is not both of length 2 and in a K3{rcub}. We show that if a connected graph G is not a path, a cycle or K1,3, then for a given s, we give the best known bound of the s-Hamiltonian index of the graph.

Share

COinS