Invariants Of Digraphs Under Tensor Product And State Splitting

As an important branch of modern mathematics, graph theory is playing more and more important roles in mathematics and other scientific fields. Since 1930 s, the research on graph theory had achieved much progress, and a lot of important results and new theories had been obtained. Especially with the development of computer science after 1970 s,graph theory was injected new vigor, and research on graph theory and its applications in physics, chemistry, computer science and many other fields had been developed surprisingly.However, research on graph theory was mainly about undirected graphs in the last century. In recent years, with the widely applications of digraphs in mathematics and many other fields, related research began to attract attention. Invariant theory is an important topic in the research of digraphs. This thesis deals with tensor product and state splitting of digraphs, and studies invariants under these two operations. The main results are as follows.In 1960 s, the invariance of strong and unilateral connectedness of digraphs under tensor product had been characterized completely. But a convenient characterization for a weakly connected tensor product, posed by Harary and Trauth in 1966, is still an open problem in the theory of digraphs. By introducing the concepts of weight and diameter for digraphs, this thesis gives a complete characterization for a weakly connected tensor product, which answers the above open problem.The primitive digraph is an important kind of digraphs, and is closely related to road coloring theorem and Markov Chains. Based on the research about conditions of weak connectedness of tensor product of digraphs, this thesis generalizes the concept of primitive digraph to generalized primitive digraph, and proves that these two concepts are equivalent for strongly connected digraphs. Moreover, an algebraic characterization of the generalized primitive digraph is given with the solvability of some T-Sylvester equations related to the incidence matrices. Meanwhile, the invariance of the primitivity and generalized primitivity of digraphs under tensor product is characterized.State splitting is an important operation of digraphs, and is closely related to symbolic dynamics. By using the structures of directed cycles and rooted forests, this thesis gives several invariants of weighted digraphs respectively under the operations of in-state splitting and out-state splitting. Meanwhile, the invariance of the primitivity and generalized primitivity of digraphs under state splitting is characterized.