Hamiltonian Cycles in the Square of a Two-Connected Graph with Given Circumference

Antoni Marczyk1
1 Instytut Matematyki AGH Krakéw, Al. Mickiewicza 30 Poland

Abstract

Let \(p\) denote the circumference of a two-connected graph \(G\). We construct a hamiltonian cycle in \(G^2\) which contains more than \(p/2\) edges of \(G\). Using this construction we prove some properties of hamiltonian cycles in the square of \(G\).