It is known that the study of the qualitative properties of a matrix A (which depend only on the sign pattern of A) can be turned into the study of the graph theoretical properties of the signed digraph S(A). The unde...It is known that the study of the qualitative properties of a matrix A (which depend only on the sign pattern of A) can be turned into the study of the graph theoretical properties of the signed digraph S(A). The underlying digraph of the signed digraph of a strong sign nonsingular matrix (abbreviated S NS matrix) with a negative main diagonal is called an S NS digraph. In the study of S NS digraphs, the minimal forbidden configuration (or MFC for short) plays an important role. Three (classes of) MFS's were constructed by Thomassen, Brualdi and Shader, and Shao. In this paper, we show that a digraph D is an S2NS digraph if and only if its 'cycle linear system' is solvable. This simplifies a parallel result obtained by Shao and Hu. As an application of the result, a graph theoretical characterization for a digraph to be an S NS digraph is given. At the end of the paper, we construct infinitely many new MFCs to show that for each even number k(k>0), there are basic MFCs with fc terminal components (here, with no loss of generality, we assume that the number of the initial components of a digraph is no less than that of its terminal components throughout the following).展开更多
基金Supported by the Doctoral Fund of the Xiamen University (No.Y01007).
文摘It is known that the study of the qualitative properties of a matrix A (which depend only on the sign pattern of A) can be turned into the study of the graph theoretical properties of the signed digraph S(A). The underlying digraph of the signed digraph of a strong sign nonsingular matrix (abbreviated S NS matrix) with a negative main diagonal is called an S NS digraph. In the study of S NS digraphs, the minimal forbidden configuration (or MFC for short) plays an important role. Three (classes of) MFS's were constructed by Thomassen, Brualdi and Shader, and Shao. In this paper, we show that a digraph D is an S2NS digraph if and only if its 'cycle linear system' is solvable. This simplifies a parallel result obtained by Shao and Hu. As an application of the result, a graph theoretical characterization for a digraph to be an S NS digraph is given. At the end of the paper, we construct infinitely many new MFCs to show that for each even number k(k>0), there are basic MFCs with fc terminal components (here, with no loss of generality, we assume that the number of the initial components of a digraph is no less than that of its terminal components throughout the following).
