×

zbMATH — the first resource for mathematics

Activity preserving bijections between spanning trees and orientations in graphs. (English) Zbl 1070.05026
Summary: The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink.

MSC:
05C05 Trees
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
05B35 Combinatorial aspects of matroids and geometric lattices
52C40 Oriented matroids in discrete geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beissinger, J.S.; Peled, U.N., A note on major sequences and external activity in trees, the Wilf festschrift (Philadelphia, PA, 1996), Electron. J. combin., 4, 2, (1997), Research Paper 4, approx. 10pp. (electronic)
[2] Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (), 123-225 · Zbl 0769.05026
[3] R. Cori, I. Le Borgne, The Sandpile model and Tutte polynomials Adv. in Appl. Math. 30 (1-2) (2003) 44-52. · Zbl 1030.05058
[4] Etienne, G.; Las Vergnas, M., External and internal elements of a matroid basis, Discrete math., 179, 111-119, (1998) · Zbl 0887.05012
[5] de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P., Bipolar orientations revisited, Discrete appl. math., 56, 157-179, (1995) · Zbl 0830.05023
[6] Gebhard, D.D.; Sagan, B.E., Sinks in acyclic orientations of graphs, J. combin. theory ser. B, 80, 130-146, (2000) · Zbl 1023.05069
[7] E. Gioan, Correspondance naturelle entre bases et réorientations des matroı¨des orientés, Thèse de Doctorat de l’Université Bordeaux 1, 2002.
[8] Gioan, E.; Las Vergnas, M., Bases, reorientations and linear programming in uniform and rank 3 oriented matroids, Adv. in appl. math., 32, 212-238, (2004), Proceedings of the Workshop on Tutte polynomials, Barcelona 2001 · Zbl 1053.05023
[9] E. Gioan, M. Las Vergnas, (Survey) On a natural correspondence between bases and reorientations, related to the Tutte polynomial and linear programming, in graphs, hyperplane arrangements, and oriented matroids, Proceedings FPSAC03, Linköping, 2003.
[10] E. Gioan, M. Las Vergnas, Activity preserving simplex-region correspondences in supersolvable arrangements of hyperplanes, submitted. · Zbl 1188.52025
[11] E. Gioan, M. Las Vergnas, An active basis-orientation correspondence in oriented matroids, submitted.
[12] Greene, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions and orientations of graphs, Trans. amer. math. soc., 280, 97-126, (1983) · Zbl 0539.05024
[13] Lass, B., Orientations acycliques et le polynôme chromatique, European J. combin., 22, 1101-1123, (2001) · Zbl 0990.05063
[14] Las Vergnas, M., The Tutte polynomial of a morphism of matroids II. activities of orientations, (), 367-380
[15] Las Vergnas, M., A correspondence between spanning trees and orientations in graphs, (), 233-238
[16] Stanley, R.P., Acyclic orientations of graphs, Discrete math., 5, 171-178, (1973) · Zbl 0258.05113
[17] Tutte, W.T., A contribution to the theory of chromatic polynomials, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101
[18] Viennot, X.G., Heaps of pieces I: basic definitions and combinatorial lemmas, combinatoire énumérative, Proc. colloq. montral can. lect. notes math., 1234, 321-350, (1986)
[19] Winder, R.O., Partitions of N-spaces by hyperplanes, SIAM J. appl. math., 14, 811-818, (1966) · Zbl 0161.13601
[20] G.J. Minty, On the axiomatic foundations of the directed linear graphs, electrical networks and network-programming, Studies in graph theory, Part II, Studies in Mathematics, Vol. 12, Mathematical Association of America, Washington DC, 1975, pp. 246-300.
[21] Bland, R.G.; Las Vergnas, M., Orientability of matroids, J. combin. theory ser. B, 24, 94-123, (1978) · Zbl 0374.05016
[22] Minty, G.J., On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming, J. math. mech., 15, 485-520, (1966) · Zbl 0141.21601
[23] Las Vergnas, M., Matroı¨des orientables, C. R. acad. sci. Paris sér. A, 280, 61-64, (1975) · Zbl 0304.05013
[24] Zaslavsky, T., Facing up to arrangements: face count formulas for partitions of space by hyperplanes, Memoirs amer. math. soc., 1, 154, (1975) · Zbl 0296.50010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.