HAMILTONIAN PROPERTIES OF FAULTY RECURSIVE CIRCULANT GRAPHS

Abstract

We present some results concerning hamiltonian properties of recursive circulant graphs in the presence of faulty vertices and/or edges. The recursive circulant graph G(N, d) with d ≥ 2 has vertex set V(G) = {0, 1, …, N - 1} and the edge set E(G) = {(v, w)| ∃ i, 0 ≤ i ≤ ⌈ log d N⌉ - 1, such that v = w + d i (mod N)}. When N = cd k where d ≥ 2 and 2 ≤ c ≤ d, G(cd k , d) is regular, node symmetric and can be recursively constructed. G(cd k , d) is a bipartite graph if and only if c is even and d is odd. Let F, the faulty set, be a subset of V(G(cd k , d)) ∪ E(G(cd k , d)). In this paper, we prove that G(cd k , d) - F remains hamiltonian if |F| ≤ deg (G(cd k , d)) - 2 and G(cd k , d) is not bipartite. Moreover, if |F| ≤ deg (G(cd k , d)) - 3 and G(cd k , d) is not a bipartite graph, we prove a more stronger result that for any two vertices u and v in V(G(cd k , d)) - F, there exists a hamiltonian path of G(cd k , d) - F joining u and v.