Characterization of signed graphs which are cellularly embeddable in no more than one surface (Q1182736): Difference between revisions

A signed graph is a graph \(G\) and a function \(f: E(G)\to\{-1,+1\}\). A cycle \((e_1,e_2,\ldots,e_k)\) of \(G\) is balanced if \(\prod^k_{i=1} f(e_i)=+1\). An imbedding \(i: G\to S\) of a connected signed graph \(G\) in a closed surface \(S\) is restricted to mean a 3-cell imbedding such that, for each cycle \(C\) in \(G\), \(C\) is balanced if and only if \(i(C)\) is an orientation-preserving curve on \(S\). It is shown that such a \(G\) imbeds in such a fashion in a unique \(S\) if and only if every two cycles of \(G\) are disjoint. A special case of this characterization gives a new proof of the characterization of \textit{E. A. Nordhaus}, \textit{R. D. Ringeisen}, \textit{B. M. Stewart} and the reviewer [J. Comb. Theory Ser. B 12, 260--267 (1972; Zbl 0217.02301)] of those connected graphs having orientable genus equal to orientable maximum genus. The additivity formula for orientable maximum genus of the same paper is also generalized.