zbMATH — the first resource for mathematics

Characterizations of some classes of strong sign nonsingular digraphs. (English) Zbl 0965.05050
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.

05C20 Directed graphs (digraphs), tournaments
05C22 Signed and weighted graphs
05C75 Structural characterization of families of graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Bassett, L.; Maybee, J.; Quirk, J., Qualitative economics and the scope of the correspondence principle, Econometrica, 36, 544-563, (1968) · Zbl 0217.26802
[2] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, The Macmillan Press Ltd., New York, 1976. · Zbl 1226.05083
[3] Brualdi, R.A.; Shader, B.L., Matrices of sign-solvable linear system, (1995), Cambridge University Press Cambridge · Zbl 0833.15002
[4] Shao, Jia-yu, Characterizations of free-cyclic digraphs, Appl. math. J. Chinese univ., 1, 2, 1-11, (1986)
[5] Shao, Jia-yu, On digraphs and forbidden configurations of strong sign nonsingular matrices, Linear algebra appl., 282, 221-232, (1998) · Zbl 0940.05044
[6] Thomassen, C., When the sign pattern of a square matrix determines uniquely the sign pattern of its inverse, Linear algebra appl., 119, 27-34, (1989) · Zbl 0673.05067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.