# Yuan-Kang Shih

## Publications

##### 3 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

**Authors:**
Shin-Shin Kao,
Yuan-Kang Shih,
Hsun Su

**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.

**Keywords:**
Hamiltonian,
complement,
degree sum,
tough

##### 2 An Improved Construction Method for MIHCs on Cycle Composition Networks

**Authors:**
Hsun Su,
Yuan-Kang Shih,
Shin-Shin Kao

**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.

**Keywords:**
Hamiltonian cycle,
k-ary n-cube,
cycle composition networks,
mutually independent

##### 1 The Spanning Laceability of k-ary n-cubes when k is Even

**Authors:**
Yuan-Kang Shih,
Shu-Li Chang,
Shin-Shin Kao

**Abstract:**

**Keywords:**
Hamiltonian,
container,
k-ary n-cube,
m*-connected

## Abstracts

##### 1 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

**Authors:**
Shin-Shin Kao,
Yuan-Kang Shih,
Hsun Su

**Abstract:**

**Keywords:**
Hamiltonian,
complement,
degree sum,
tough