The Minimum Rank Of The Special Symbols Mode

The minimum rank problems of sign patterns play an important role in the fields such as singular graph theory, hermitian rank and the computation of the communication complexity. Using graph, the minimum rank and the semi-definite rank for combinatorial symmetric sign patterns are discussed.The development of minimum rank problem is introduced. The equivalence between the sign pattern and graph is also given, that is to say, the study of minimum rank problem for sign pattern and that for graph is equivalent under some special conditions.Combinatorial symmetric sign patterns are considered. What we concerned more is the symmetric minimum rank. Firstly, we introduce several definitions and related results, based on which we obtain a lower bound of the minimum rank for particular sign patterns. More specifically, we show that the minimal rank equal to zero forcing number for graphs such as C_t ( K_r),S_t ( K_r),C_t ( K_r)-u,S_t( K₃) -v .Secondly, we prove that the minimal rank of Halin graph constructed by a star or a double star is the order of the graph minus three. In addition, the minimum rank of the lotus leaf withm outer vertices is m . In the end, the minimum rank for skew-symmetric sign pattern is considered. We obtain the minimum rank for M&o&b ius ladderand the Corora of two paths.The definition of the minimum semi-definite rank is introduced. The upper and lower bound of minimum semi-definite rank is discussed. A method for constructing an OS-set is proposed, and a lower bound of minimum semi-definite rank for bipartite graph is extended to general graphs. Moreover, the minimum semi-definite rank for the sign patterns corresponding to k-regular graph and K_n which satisfy the equationmsr(G ) = ts(G ) - 1.