On Theorems Equivalent with Kotzig’s Result on Graphs with Unique \(1\)-Factors

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 < 2\) but are NP-complete for \(p \geq 2\).