×

Flows on hypermaps. (English) Zbl 0633.05053

A flow in an oriented graph has traditionally been defined as a function from the set of edges to the nonnegative reals such that the sum of the values on the edges entering any vertex equals that on the edges leaving it (Kirchhoff’s Law) [L. R. Ford jun. and D. R. Fulkerson, “Flows in Networks” (1962; Zbl 0106.348)] - for a 2-pole network this can be arranged by joining the sink to the source by an arc containing the net flow. If the function is redefined on the set B of vertex-edge incidence pairs (called brins in the paper under review) by making the value on an oriented edge positive at the tail end and negative at the head end, then the sum is zero both for all the brins in each vertex and for all (i.e., both) the brins in each edge. This definition is extended to hypergraphs (in which each edge can have an arbitrary number of brins) and then to hypermaps (in which the brins at each edge and at each vertex are assigned a cyclic order, so that the vertices and edges become the cycles of the permutations \(\sigma\) and \(\alpha\) on B [R. Cori, “Un code pour les graphes planaires et ses applications“, Astérisque 27 (1975; Zbl 0313.05115)]), and also to an arbitrary field K instead of the reals, and stated in the language of vector spaces as follows. Let K(B) be the space of functions from B to K, and let S and A be the subspaces of K(B) which fix \(\sigma\) and \(\alpha\), respectively. Then the space of flows of the hypermap (\(\sigma\),\(\alpha)\) is \(S^{\perp}\cap A^{\perp}.\)
To associate a flow with a face (a cycle of \(\sigma\alpha)\), a function \(\phi\) : \(B\to K(B)\) is defined to be \(\phi (i)=i\theta - (i\theta)\alpha^{-1}\), where \(i\theta\) is the sum of the elements in the face containing i. It is shown that if the hypermap (\(\sigma\),\(\alpha)\) is of genus g, then \(\dim ((S^{\perp}\cap A^{\perp})/Im \phi)=2g.\)
It is also shown that if (\(\sigma\),\(\alpha)\) has only one face, then the space of flows is generated by \(U(i)=i\theta -(i\theta)\alpha^{-1}\), \(i\in B\), where \(i\theta\) now means the sum of the elements in the cycle of \(\sigma\alpha\tau\) containing \(i: \tau\) is the transposition (i,\(\alpha\) (i)). When this result is specialized to maps (i.e., when \(\alpha\) is a fixed-point-free involution), a result contained in [H. R. Brahana, “Systems of circuits on two-dimensional manifolds”, Ann. Math. 23, 144-168 (1921; F.d.M. 48, 661)] is retrieved. Finally, a basis for the space of flows in an arbitrary hypermap is constructed.
Reviewer: T.Walsh

MSC:

05C65 Hypergraphs
90B10 Deterministic network models in operations research
05C10 Planar graphs; geometric and topological aspects of graph theory
15A03 Vector spaces, linear dependence, rank, lineability
Full Text: DOI

References:

[1] DOI: 10.1016/0097-3165(72)90010-6 · Zbl 0314.05005 · doi:10.1016/0097-3165(72)90010-6
[2] DOI: 10.2307/1968030 · JFM 48.0661.02 · doi:10.2307/1968030
[3] Biggs, Algebraic graph theory (1974) · Zbl 0797.05032 · doi:10.1017/CBO9780511608704
[4] DOI: 10.1016/0095-8956(75)90042-8 · Zbl 0302.05101 · doi:10.1016/0095-8956(75)90042-8
[5] Cori, Un code pour les graphes planaires et ses applications (1975) · Zbl 0313.05115
[6] Tutte, Graph Theory, Encyclopedia of Mathematics and its Applications 21 (1984)
[7] Cori, Boll. Un. Mat. Ital. 18 pp 84– (1981)
[8] DOI: 10.1007/BF01191186 · Zbl 0522.20003 · doi:10.1007/BF01191186
[9] DOI: 10.1112/plms/s3-37.2.273 · Zbl 0391.05024 · doi:10.1112/plms/s3-37.2.273
[10] Jaeger, Progress in graph theory (Waterloo, Oct. 1982 pp 347– (1984)
[11] Jacques, C. R. Acad. Sci. Paris 267 pp 625– (1968)
[12] Edmonds, Notices Amer. Math. Soc. 7 pp 646– (1960)
[13] Cori, European J. Combin. 2 pp 331– (1981) · Zbl 0472.05049 · doi:10.1016/S0195-6698(81)80039-X
[14] Ringel, Map colour theorem (1974) · doi:10.1007/978-3-642-65759-7
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.