The flow and tension spaces and lattices of signed graphs. (English) Zbl 1198.05085
Summary: This paper is to introduce circuit, bond, flow, and tension spaces and lattices for signed graphs, and to study the relations among these spaces and lattices. The key ingredient is to introduce circuit and bond characteristic vectors so that the desired spaces and lattices can be defined such that their dimensions and ranks match well to that of matroids of signed graphs. The main results can be stated as follows: (1) the classification of minimal directed cuts; (2) the circuit space (lattice) equals flow space (lattice), and the bond space equals the tension space; (3) the bond lattice equals the row lattice of the incidence matrix, and the reduced bond lattice equals the tension lattice; and (4) for unbalanced signed graphs, the module of potentials is isomorphic to the module of tensions if the coefficient ring is 2-torsion free.
MSC:
| 05C22 | Signed and weighted graphs |
Keywords:
circuit spaces; bond spaces; flow spaces; tension spaces; lattices; signed graphs; characteristic vectors; minimal directed cuts; bond lattice; row lattice; incidence matrixReferences:
| [1] | Beck, M.; Zaslavsky, T., The number of nowhere-zeo flows on graphs and signed graphs, J. Combin. Theory Ser. B, 96, 901-918 (2006) · Zbl 1119.05105 |
| [2] | Beck, M.; Zaslavsky, T., Inside-out polytopes, Adv. Math., 205, 134-162 (2006) · Zbl 1107.52009 |
| [3] | Berge, C., Graphs and Hypergraphs (1973), American Elsevier: American Elsevier New York · Zbl 0483.05029 |
| [4] | Bollobás, B., Modern Graph Theory (1998), Springer · Zbl 0902.05016 |
| [5] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North Holland: North Holland New York · Zbl 1134.05001 |
| [6] | Bouchet, A., Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B, 34, 279-292 (1983) · Zbl 0518.05058 |
| [7] | Godsil, C.; Royle, G., Algebraic Graph Theory (2004), Springer |
| [8] | Khelladi, A., Nowhere-zero integral chains and flows in bidirected graphs, J. Combin. Theory Ser. B, 43, 95-115 (1987) · Zbl 0617.90026 |
| [9] | Zaslavsky, T., The geometry of root systems and signed graphs, Amer. Math. Monthly, 88, 88-105 (1981) · Zbl 0466.05058 |
| [10] | Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 47-74 (1982) · Zbl 0476.05080 |
| [11] | Zaslavsky, T., Signed graph colorings, Discrete Math., 39, 215-228 (1982) · Zbl 0487.05027 |
| [12] | Zaslavsky, T., Orientation of signed graphs, European J. Combin., 12, 361-375 (1991) · Zbl 0761.05095 |
| [13] | Zaslavsky, T., A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin., 5 (1998), Dynamic Surveys 8, 124 pp. (electronic) · Zbl 0898.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
