Characterizations of some classes of strong sign nonsingular digraphs (Q1582078)

All graphs treated in this paper are finite and directed. A signed digraph \(S\) is a digraph where each arc is assigned a sign \(+1\) or \(-1\). The sign of a subdigraph \(S_1\) of \(S\) is defined to be the product of the signs of all arcs of \(S_1\). \(S\) is called a strong sign nonsingular \((\text{S}^2\text{NS})\) signed digraph if the sign of every cycle of \(S\) is negative and if every pair of paths in \(S\) with the same initial vertex and the same terminal vertex have the same sign. There also exists a relationship with strong sign nonsingular matrices, these are such square real matrices with a negative main diagonal which are associated to an \(\text{S}^2\text{NS}\) signed digraph. A digraph \(D\) is called an \(\text{S}^2\text{NS}\) underlying digraph or simply \(\text{S}^2\text{NS}\) digraph if the arcs of \(D\) can be suitably assigned the signs so that the resulting signed digraph is an \(\text{S}^2\text{NS}\) signed digraph and a digraph which is not an \(\text{S}^2\text{NS}\) signed digraph is called a forbidden configuration. If \(D\) is a forbidden configuration, but any proper subdigraph of \(D\) is not a forbidden configuration, then \(D\) is called a minimal forbidden configuration. The authors introduce certain operations on digraphs (the splitting on a vertex of \(D\) and the subdivision on an arc of \(D\)) which can preserve the property of being, or not being, an \(\text{S}^2\text{NS}\) signed digraph, and they get necessary and sufficient conditions in terms of forbidden configurations for two classes of digraphs to be \(\text{S}^2\text{NS}\) signed digraphs. At first the authors obtain two necessary conditions with the help of three examples given in the paper, Examples 1.1, 1.2 and 1.3, namely: (1) The digraph \(D\) contains no arc subdivisions of a digraph \(D_3\) (with three vertices and four arcs in Example 1.1) and of it reverse digraph \(D_3'\), which both are minimal forbidden configurations. (2) \(D\) contains no subdigraph which can be obtained from a digraph \(D_1\) given in Example 1.3 or its reverse graph by finitely many steps of splittings and subdivisions. By an example it is shown that these conditions are still not sufficient for digraphs in general. The main result of the paper consists in a proof of the statement that the necessary conditions for \(\text{S}^2\text{NS}\) digraphs given above are also sufficient for the following two special classes of digraphs: (a) the class of a generalization of the family of the digraphs \(D_1\) given in Example 1.3 (Theorem 2.1), and (b) the class of digraphs which contain at most two terminal (or two initial) components and contain no arcs between different intermediate components (Theorem 3.1); this class is a further generalization of the class in Theorem 2.1.