Characterizations of some classes of strong sign nonsingular digraphs

DOI10.1016/S0166-218X(00)00182-7MaRDI QIDQ1582078zbMATH OpenWikidataFDO

Publication date 27 February 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00182-7

forbidden configuration signed digraph strong sign nonsingular matrices

Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Characterizations of some classes of strong sign nonsingular digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582078)