The fundamental concepts of graph theory are cycles, Eulerian graphs, bonds, cuts, spanning trees and orientations, and so on. In addition to these concepts there are two important vector spaces associated with graphs, namely, the cycle space and the bond space; they are subspaces of the Euclidean space of all real-valued functions defined on the edge set of a given graph. It is well-known that the cycle space and the bond space are orthogonal complements of each other, and the dimensions of these spaces count the number of independent cycles and the number of independent bonds, respectively. One classical result of graph theory is the Kirchoff Matrix-Tree Formula, which counts the number of spanning trees of a given graph by the determinants of the cycle lattice and the bond lattice....[ Read more ]

The fundamental concepts of graph theory are cycles, Eulerian graphs, bonds, cuts, spanning trees and orientations, and so on. In addition to these concepts there are two important vector spaces associated with graphs, namely, the cycle space and the bond space; they are subspaces of the Euclidean space of all real-valued functions defined on the edge set of a given graph. It is well-known that the cycle space and the bond space are orthogonal complements of each other, and the dimensions of these spaces count the number of independent cycles and the number of independent bonds, respectively. One classical result of graph theory is the Kirchoff Matrix-Tree Formula, which counts the number of spanning trees of a given graph by the determinants of the cycle lattice and the bond lattice.

Turning from graphs to signed graphs, it is natural to ask whether the concepts and the results for graphs can be generalized to signed graphs. Guided by matroid theory, Zaslavsky naturally extended the concepts of graph theory such as cycles, bonds, and orientations, etc, to signed graphs. In particular, he obtained an analogy of Kirchoff's Matrix-Tree Formula for unbalanced signed graphs. In this thesis, I shall follow Zaslavsky's approach to signed graphs to further extend the fundamental concepts and results about graphs to signed graphs.

Following Zaslavsky's notions of circuits, bonds, directed circuits, and directed bonds, I first introduce characteristic vectors of directed circuits and directed bonds. Then I introduce the circuit space and bond space, flow space and tension space, and the flow lattice and tension lattice of signed graphs. With these notions of signed graphs, the main results of the thesis are as follows.

(1) The circuit space of a signed graph is the span of all characteristic vectors of directed circuit, which is a subspace of the Euclidean space of all real-valued functions defined on the edge set of a given signed graph. Similarly, the bond space is the span of all characteristic vectors of directed bonds. The first main result is the orthogonality of the circuit space and the bond space of a signed graph, similar to that for ordinary graphs. The dimensions of the circuit space and the bond space count the number of independent circuits and the number of independent bonds of signed graphs.

(2) The flow space is defined to be the vector space of all real-valued functions that are conservative at every vertex of a given signed graph. The tension space is defined as the orthogonal complement of the circuit space. It turns out that the flow space and the tension space are orthogonal complements of each other. It is shown in this thesis that the flow space is the same as the circuit space and the tension space is the same as the bond space. This is similar to that of ordinary graphs.

(3) For non-negative integral flows I introduce minimal flows and characterize their patterns. The next main result of the thesis is the classification of minimal flows by the Minimal Flow Reduction Algorithm. A notable feature is that the minimal flows for ordinary graphs are the same as the characteristic vectors of circuits. However, for unbalanced signed graphs, the minimal flows have a variety of patterns that cannot be found in ordinary graphs. This is one of the main difference between ordinary graphs and signed graphs.

(4) In ordinary graphs, there is a projection from the coloring space onto the tension space by the difference operator. The projection is a homomorphism with a nontrivial kernel. For a connected unbalanced signed graph, we have a similar difference operator from the coloring space to the tension space; however, this difference operator is an isomorphism. This is another main difference between ordinary graphs and signed graphs.

(5) I introduce a new concept, torsion, for signed graph in my thesis. The torsion of a signed graph is the torsion of its incidence matrix. In ordinary graphs, the matrices obtained from spanning trees are unimodular, that is, non-zero submatrices of any such matrix have torsion 1. However, for unbalanced signed graphs, the torsion of such matrices obtained from maximal forest need not be 1; the torsion depends on the number of edges on the unbalanced cycles of a given maximal forest.

(6) The final result of the thesis is about the unification of the Kirchoff Matrix-Three Formula for ordinary graphs and the analogue of Zaslavsky's formula for an unbalanced signed graph by using the concept of torsion.