Characterizations of some classes of strong sign nonsingular digraphs
type: Item
instance of: scholarly article
title: Characterizations of some classes of strong sign nonsingular digraphs
zbMATH Open document ID: 0965.05050
DOI: 10.1016/S0166-218X(00)00182-7
author: Zhixiang Hu
author: Jia-Yu Shao
published in: Discrete Applied Mathematics
publication date: 2001-02-27T00:00:00Z
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 whic…
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1512453
zbMATH Keywords: signed digraph
zbMATH Keywords: strong sign nonsingular matrices
zbMATH Keywords: forbidden configuration
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Qualitative Economics and the Scope of the Correspondence Principle
cites work: Q3097395
cites work: Q4858123
cites work: On digraphs and forbidden configurations of strong sign nonsingular matrices
cites work: When the sign pattern of a square matrix determines uniquely the sign pattern of its inverse
Wikidata QID: Q126465247
description: scientific article; zbMATH DE number 1512453