Super Connectivity, Fault-Tolerant Hamiltonicity, and Bipancyclicity for Some Interconnection Networks
| Autor: | Y-Chuang Chen, 陳玉專 |
|---|---|
| Rok vydání: | 2003 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 92 Let $G=(V,E)$ be a $k$-regular graph with connectivity $\kappa$ and edge connectivity $\lambda$. $G$ is {\it maximum connected} if $\kappa = k$, and $G$ is {\it maximum edge connected} if $\lambda = k$. Moreover, $G$ is {\it super-connected} if it is a complete graph, or it is maximum connected and every minimum vertex cut is $\{x \mid (v,x) \in E \}$ for some vertex $v \in V$; and $G$ is {\it super-edge-connected} if it is maximum edge connected and every minimum edge disconnecting set is $\{(v, x) \mid (v,x) \in E \}$ for some vertex $v \in V$. In this thesis, we present three chemes to construct graphs which are super-connected an super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, m\"{o}bius cubes, split-stars, and recursive circulant graphs \cite{amc1}. Besides connectivity, the hamiltonian property is also a major requirement in design the topology of networks. \sp4 A $k$-regular hamiltonian and hamiltonian connected graph $G$ is {\it super fault-tolerant hamiltonian} if $G$ remains hamiltonian after removing at most $k-2$ vertices and/or edges and remains hamiltonian connected after removing at most $k-3$ vertices and/or edges. We also investigate some construction schemes to construct super fault-tolerant hamiltonian graphs; and twisted cubes, crossed cubes, m\"{o}bius cubes, and recursive circulant graphs are specific cases of our construction schemes \cite{hamilProc,amc2}. We note that these graphs are not bipartite. \sp4 In this thesis, we also study some {\it hamiltonian} roperties of bipartite graphs. Every hamiltonian {\it bipartite graph} $G = (V_0 \cup V_1, E)$ satisfies $|V_0|=|V_1|$. Since the colors of a path in bipartite graphs alternate, any hamiltonian bipartite graphs cannot be {\it hamiltonian connected}. Thus, the concepts of {\it hamiltonian laceability}, {\it strongly hamiltonian laceability}, {\it hyper-hamiltonian laceability}, {\it bipancyclicity}, and {\it edge-bipancyclicity} for hamiltonian bipartite graphs are attractive topics in interconnection networks. In this thesis, we propose several methods, which extend the result in \cite{Harary}, to construct hamiltonian laceable, strongly hamiltonian laceable, and hyper-hamiltonian laceable graphs. We show that our construction schemes preserve bipancyclic and edge-bipancyclic properties \cite{congressus}. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|