Abstract: In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.
Abstract: Qk
n has been shown as an alternative to the hypercube
family. For any even integer k ≥ 4 and any integer n ≥ 2, Qk
n is
a bipartite graph. In this paper, we will prove that given any pair of
vertices, w and b, from different partite sets of Qk
n, there exist 2n
internally disjoint paths between w and b, denoted by {Pi | 0 ≤ i ≤ 2n-1}, such that 2n-1
i=0 Pi covers all vertices of Qk
n. The result is
optimal since each vertex of Qk
n has exactly 2n neighbors.
Abstract: Many well-known interconnection networks, such as kary n-cubes, recursive circulant graphs, generalized recursive circulant graphs, circulant graphs and so on, are shown to belong to the family of cycle composition networks. Recently, various studies about mutually independent hamiltonian cycles, abbreviated as MIHC-s, on interconnection networks are published. In this paper, using an improved construction method, we obtain MIHC-s on cycle composition networks with a much weaker condition than the known result. In fact, we established the existence of MIHC-s in the cycle composition networks and the result is optimal in the sense that the number of MIHC-s we constructed is maximal.