TTuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài:the Prism of the Acyclic Orientati. | The Prism of the Acyclic Orientation Graph is Hamiltonian GARA PRUESSE Department of Computer Science and Electrical Engineering University of Vermont Burlington VT 05405-0156 USA email gara@ .edu Frank RusKEy t Department of Computer Science University of Victoria Victoria . V8W 3P6 Canada email fruskey@ Submitted December 20 1994 Accepted March 13 1995. Abstract Every connected simple graph G has an acyclic orientation. Define a graph AO G whose vertices are the acyclic orientations of G and whose edges join orientations that differ by reversing the direction of a single edge. It was known previously that AO G is connected but not necessarily Hamiltonian. However Squire 3 proved that the square AO G 2 is Hamiltonian. We prove the slightly stronger result that the prism AO G X e is Hamiltonian. If G is a mixed graph some edges directed but not necessarily all then AO G can be defined as before. The graph AO G is again connected but we give examples showing that the prism is not necessarily Hamiltonian. This material is based upon work supported by the National Science Foundation under Grant No. NSF OSR-9350540. 1 Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 1995 R5 2 1 Introduction Every connected simple graph G has an acyclic orientation. Define a graph AO G whose vertices are the acyclic orientations of G and whose edges join orientations that differ by reversing the direction of a single edge. Squire Savage and West 4 show that AO G is connected and bipartite and discuss the Hamiltonicity of AO G for well-known types of graphs such as trees cycles wheels and ladders. Squire 3 proved that the square AO G 2 is Hamiltonian. Our main goal in this paper is to prove the slightly stronger result that the prism AO G X e is Hamiltonian. If the prism of a bipartite graph is Hamiltonian then the square of the graph is Hamiltonian. If G is a
