Characterization of Graphs Without Even F‐Orientations

ABSTRACT A graph is 1‐extendable if every edge belongs to at least one 1‐factor of . Let be a graph with a 1‐factor . Then an even (odd) ‐orientation of is an orientation in which each ‐alternating cycle has exactly an even (odd) number of edges directed in the same fixed direction around the cycle. If a graph admits an odd ‐orientation for some 1‐factor then it admits an odd ‐orientation for all 1‐factors . Such graphs are called Pfaffian and have been widely studied. A similar statement is not true for even ‐orientations, of which little is known. The purpose of this paper is to achieve helpful results about even ‐orientations. In particular, we examine the structure of 1‐extendable graphs which have no even ‐orientations for a fixed 1–factor of . Such graphs contain a special subgraph in a family that we will call generalized Wagner graphs . We give a complete characterization of generalized Wagner graphs without even orientations in the case of connectivity at least four and in the case of ‐regular graphs for .