×

zbMATH — the first resource for mathematics

Enumerating degree sequences in digraphs and a cycle–cocycle reversing system. (English) Zbl 1114.05024
Summary: We give some new enumerations of indegree sequences of orientations of a graph using the Tutte polynomial. Then we introduce some discrete dynamical systems in digraphs consisting in reversing cycles, cocycles, or both, which extend the edge firing game (reversing sinks) by considering all orientations (reversing cocycles) and by introducing duality (reversing cycles). We show that indegree sequences can represent the configurations of these systems, and we enumerate equivalence classes of these systems. In particular, concerning the cycle–cocycle reversing system, we show that its configurations are in bijection with indegree sequences of orientations having a given vertex (quasi-sink of the system) reachable from any other. We also briefly discuss its generalization to oriented matroids, and relate structural and enumerative properties of its configurations to those of the sandpile model or chip firing game.

MSC:
05C07 Vertex degrees
05C20 Directed graphs (digraphs), tournaments
52C40 Oriented matroids in discrete geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bak, P., How nature works — the science of SOC, (1997), Oxford University Press UK
[2] Biggs, N., Chip firing and the critical group of a graph, J. algebraic combin., 9, 25-45, (1999) · Zbl 0919.05027
[3] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G., Oriented matroids, (), 1999
[4] Björner, A.; Lovász, L.; Shor, P.W., Chip firing games on graphs, European J. combin., 12, 283-291, (1991) · Zbl 0729.05048
[5] Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (), (Chapter 6) · Zbl 0769.05026
[6] Cori, R.; Le Borgne, I., The sandpile model and Tutte polynomials, Adv. appl. math., 30, 1-2, 44-52, (2003) · Zbl 1030.05058
[7] Cori, R.; Rossin, D., On the sandpile group of dual graphs, European J. combin., 21, 4, 447-459, (2000) · Zbl 0969.05034
[8] Cori, R.; Rossin, D.; Salvy, B., Polynomial ideals for sandpiles and their Gröbner bases, Theoret. comput. sci., 276, 1-2, 1-15, (2002) · Zbl 1002.68105
[9] Dhar, D., Self-organized critical state of sandpile automaton models, Phys. rev. lett., 64, (1990) · Zbl 0943.82553
[10] Etienne, G., On the Möbius algebra geometric lattices, European J. combin., 19, 921-933, (1998) · Zbl 0923.06006
[11] Etienne, G.; Las Vergnas, M., External and internal elements of a matroid basis, Discrete math., 179, 111-119, (1999) · Zbl 0887.05012
[12] E. Gioan, Circuit – cocircuit reversing system in regular matroids, Ann. Combin. (in press) · Zbl 1228.05111
[13] Gioan, E.; Las Vergnas, M., Active bijections between spanning trees and orientations in graphs, Discrete math., 298, 169-188, (2005) · Zbl 1070.05026
[14] E. Gioan, M. Las Vergnas, The active bijection in oriented matroids, II — Decompositions of activities (submitted for publication). See also chapter 2 in: Correspondance naturelle entre bases et réorientations des matroïdes orientés, Ph.D. Dissertation, Bordeaux 1 University, France, December, 2002
[15] 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
[16] Kook, W.; Reiner, V.; Stanton, D., Combinatorial Laplacians of matroid complexes, J. amer. math. soc., 13, 129-148, (1999) · Zbl 0940.05021
[17] Latapy, M.; Magnien, C., Coding distributive lattices with edge firing games, Inform. process. lett., 83, 3, 125-128, (2002) · Zbl 1043.68080
[18] Las Vergnas, M., The Tutte polynomial of a morphism of matroids II. activities of orientations, (), 367-380
[19] Merino-López, C., Chip firing and Tutte polynomial, Ann. combin., 2, 253-259, (1997) · Zbl 0901.05004
[20] 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
[21] Stanley, R.P., Acyclic orientations of graphs, Discrete math., 5, 171-178, (1973) · Zbl 0258.05113
[22] Stanley, R.P., Decompositions of rational convex polytopes, Ann. discrete math., 6, 333-342, (1980) · Zbl 0812.52012
[23] Tutte, W.T., A contribution to the theory of chromatic polynomials, Canad. 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. 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.