DISJOINT HAMILTONIAN CYCLES IN FAN 2K-TYPE GRAPHS

Abstract

AbstractIt is conjectured that a 2(k + 1)‐connected graph of order p contains k + 1 pairwise disjoint Hamiltonian cycles if no two of its vertices that have degree less than 1/2 + 2k are distance two apart. This is proved in detail for k = 1. Similar arguments establish the conjecture for k = 2. © 1993 John Wiley & Sons, Inc.