Dualities and reciprocities on graphs on surfaces. (English) Zbl 1497.05054
Summary: We extend the duality between acyclic orientations and totally cyclic orientations on planar graphs to dualities on graphs on orientable surfaces by introducing boundary acyclic orientations and totally bi-walkable orientations. In addition, we provide a reciprocity theorem connecting local tensions and boundary acyclic orientations. Furthermore, we define the balanced flow polynomial which is connected with tension polynomial by duality and with totally bi-walkable orientations by reciprocity.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C21 | Flows in graphs |
| 57M15 | Relations of low-dimensional topology with graph theory |
Keywords:
graph on a surface; tension; flow; acyclic orientation; totally cyclic orientation; duality; Ehrhart theory; combinatorial reciprocityReferences:
| [1] | Beck, M.; Zaslavsky, T., Inside-out polytopes, Adv. Math., 205, 1, 134-162 (2006) · Zbl 1107.52009 |
| [2] | Beck, M.; Zaslavsky, T., The number of nowhere-zero flows on graphs and signed graphs, J. Comb. Theory, Ser. B, 96, 901-918 (2006) · Zbl 1119.05105 |
| [3] | Breuer, F.; Sanyal, R., Ehrhart theory, modular flow reciprocity, and the Tutte polynomial, Math. Z., 270, 1-2, 1-18 (2012) · Zbl 1235.05070 |
| [4] | Devos, M.; Goddyn, L.; Mohar, B.; Vertigan, D.; Zhu, X., Coloring-flow duality of embedded graphs, Trans. Am. Math. Soc., 357, 10, 3993-4016 (2005) · Zbl 1065.05034 |
| [5] | Ellis-Monaghan, J.; Moffatt, I., Graphs on Surfaces: Dualities, Polynomials, and Knots (2013), Springer · Zbl 1283.57001 |
| [6] | Goodall, A.; Krajewski, T.; Regts, G.; Vena, L., A Tutte polynomial for maps, Comb. Probab. Comput., 27, 6, 913-945 (2018) · Zbl 1402.05107 |
| [7] | Goodall, A.; Litjens, B.; Regts, G.; Vena, L., A Tutte polynomial for maps II: the non-orientable case, Eur. J. Comb., 86, Article 103095 pp. (2020) · Zbl 1437.05108 |
| [8] | Greene, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Am. Math. Soc., 280, 1, 97-126 (1983) · Zbl 0539.05024 |
| [9] | Hwang, B.; Jung, W.; Lee, K.; Oh, J.; Yu, S., Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, J. Comb. Theory, Ser. B, 149, 52-75 (2021) · Zbl 1466.05071 |
| [10] | Kochol, M., Polynomials associated with nowhere-zero flows, J. Comb. Theory, Ser. B, 84, 260-269 (2002) · Zbl 1027.05080 |
| [11] | Noy, M., Acyclic and totally cyclic orientations in planar graphs, Am. Math. Mon., 108, 1, 66-68 (2001) · Zbl 1008.05036 |
| [12] | Stanley, R., Acyclic orientations of graphs, Discrete Math., 5, 2, 171-178 (1973) · Zbl 0258.05113 |
| [13] | Stanley, R., A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111, 1, 166-194 (1995) · Zbl 0831.05027 |
| [14] | Tutte, W., A ring in graph theory, Math. Proc. Camb. Philos. Soc., 43, 1, 26-40 (1947) · Zbl 0031.41803 |
| [15] | Tutte, W., On the imbedding of linear graphs in surfaces, Proc. Lond. Math. Soc., 51, 474-483 (1950) · Zbl 0033.30803 |
| [16] | Tutte, W., A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80-91 (1954) · Zbl 0055.17101 |
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.
