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\ge 2$.