On Theorems Equivalent with Kotzig's Result on Graphs with Unique 1-FactorsArs Combinatoria vol. 73, pp. 53-64, 2004. Download: [paper ps] [paper pdf] Abstract:We show that several known theorems on graphs and digraphs are equivalent. The list of equivalent theorems include Kotzig's result on graphs with unique 1-factors, a lemma by Seymour and Giles, theorems on alternating cycles in edge-colored graphs, and a theorem on semicycles in digraphs.We consider computational problems related to the quoted results; all these problems ask whether a given (di)graph contains a cycle satisfying certain properties which runs through p prescribed vertices. We show that all considered problems can be solved in polynomial time for p=0,1 but are NP-complete for p=2 or greater. [back to Stefan Szeider's homepage] |