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: This paper reviews the crucial situation in higher education in Taiwan due to the rapid decline of the birth rate in the past three decades, and how the government and local colleges/universities work to face the challenge. Recruiting international students is one of the possible ways to resolve the problem, but offering enough courses in English is one of the main obstacles when the majority of learners are still Taiwanese students. In the academic year of 2012, Chung Yuan Christian University determined to make its campus international and began to enforce two required courses for freshmen taught in English. It failed in the beginning, but succeeded in the following academic year of 2013. Using the teaching evaluations accumulated in the past three years, this paper aims to clarify the myths which had been bothering most faculties. It also offers some suggestions for college/university teachers interested in giving lectures in English to English as Second Language (ESL) learners. A conclusion is presented at the end of the paper, in which the author explained why Taiwanese students could learn their profession in English.
Abstract: In this paper, a thorough review about dual-cubes, DCn,
the related studies and their variations are given. DCn was introduced
to be a network which retains the pleasing properties of hypercube Qn
but has a much smaller diameter. In fact, it is so constructed that the
number of vertices of DCn is equal to the number of vertices of Q2n
+1. However, each vertex in DCn is adjacent to n + 1 neighbors and
so DCn has (n + 1) × 2^2n edges in total, which is roughly half the
number of edges of Q2n+1. In addition, the diameter of any DCn is 2n
+2, which is of the same order of that of Q2n+1. For selfcompleteness,
basic definitions, construction rules and symbols are
provided. We chronicle the results, where eleven significant theorems
are presented, and include some open problems at the end.
Abstract: Given a graph G. A cycle of G is a sequence of
vertices of G such that the first and the last vertices are the same.
A hamiltonian cycle of G is a cycle containing all vertices of G.
The graph G is k-ordered (resp. k-ordered hamiltonian) if for any
sequence of k distinct vertices of G, there exists a cycle (resp.
hamiltonian cycle) in G containing these k vertices in the specified
order. Obviously, any cycle in a graph is 1-ordered, 2-ordered and 3-
ordered. Thus the study of any graph being k-ordered (resp. k-ordered
hamiltonian) always starts with k = 4. Most studies about this topic
work on graphs with no real applications. To our knowledge, the
chordal ring families were the first one utilized as the underlying
topology in interconnection networks and shown to be 4-ordered.
Furthermore, based on our computer experimental results, it was
conjectured that some of them are 4-ordered hamiltonian. In this
paper, we intend to give some possible directions in proving 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: The hypercube Qn is one of the most well-known
and popular interconnection networks and the k-ary n-cube Qk
n is
an enlarged family from Qn that keeps many pleasing properties
from hypercubes. In this article, we study the panpositionable
hamiltonicity of Qk
n for k ≥ 3 and n ≥ 2. Let x, y of V (Qk
n)
be two arbitrary vertices and C be a hamiltonian cycle of Qk
n.
We use dC(x, y) to denote the distance between x and y on the
hamiltonian cycle C. Define l as an integer satisfying d(x, y) ≤ l ≤ 1
2 |V (Qk
n)|. We prove the followings:
• When k = 3 and n ≥ 2, there exists a hamiltonian cycle C
of Qk
n such that dC(x, y) = l.
• When k ≥ 5 is odd and n ≥ 2, we request that l /∈ S
where S is a set of specific integers. Then there exists a
hamiltonian cycle C of Qk
n such that dC(x, y) = l.
• When k ≥ 4 is even and n ≥ 2, we request l-d(x, y) to be
even. Then there exists a hamiltonian cycle C of Qk
n such
that dC(x, y) = l.
The result is optimal since the restrictions on l is due to the
structure of Qk
n by definition.
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.