×

An algebraic representation of graphs and applications to graph enumeration. (English) Zbl 1267.05179

Summary: We give a recursion formula to generate all the equivalence classes of connected graphs with coefficients given by the inverses of the orders of their groups of automorphisms. We use an algebraic graph representation to apply the result to the enumeration of connected graphs, all of whose biconnected components have the same number of vertices and edges. The proof uses Abel’s binomial theorem and generalizes Dziobek’s induction proof of Cayley’s formula.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. C. Read, “A survey of graph generation techniques,” in Combinatorial Mathematics 8, vol. 884 of Lecture Notes in Math., pp. 77-89, Springer, Berlin, Germany, 1981. · Zbl 0471.05023 · doi:10.1007/BFb0091809
[2] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, New York, NY, USA, 1973. · Zbl 0321.05130
[3] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, vol. 67, Cambridge University Press, Cambridge, UK, 1998. · Zbl 0973.20004 · doi:10.1006/jabr.1998.7428
[4] C. Itzykson and J. B. Zuber, Quantum Field Theory, McGraw-Hill, New York, NY, USA, 1980. · Zbl 0453.05035
[5] C. Jordan, “Sur les assemblages de lignes,” Journal für die Reine und Angewandte Mathematik, vol. 70, pp. 185-190, 1869. · JFM 02.0344.01
[6] R. C. Read, “Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. Algorithmic aspects of combinatorics (Conference in Vancouver Island, BC, Canada, 1976),” Annals of Discrete Mathematics, vol. 2, pp. 107-120, 1978. · Zbl 0392.05001 · doi:10.1016/S0167-5060(08)70325-X
[7] Â. Mestre and R. Oeckl, “Combinatorics of n-point functions via Hopf algebra in quantum field theory,” Journal of Mathematical Physics, vol. 47, no. 5, p. 052301, 16, 2006. · Zbl 1111.81121 · doi:10.1063/1.2196239
[8] Â. Mestre and R. Oeckl, “Generating loop graphs via Hopf algebra in quantum field theory,” Journal of Mathematical Physics, vol. 47, no. 12, Article ID 122302, p. 14, 2006. · Zbl 1112.81081 · doi:10.1063/1.2390657
[9] Â. Mestre, “Combinatorics of 1-particle irreducible n-point functions via coalgebra in quantum field theory,” Journal of Mathematical Physics, vol. 51, no. 8, Article ID 082302, 2010. · Zbl 1312.81111 · doi:10.1063/1.3449321
[10] O. Dziobek, “Eine formel der substitutionstheorie,” Sitzungsberichte der Berliner Mathematischen Gesellschaft, vol. 17, pp. 64-67, 1947. · JFM 46.0106.03
[11] A. Cayley, “A theorem on trees,” Quarterly Journal of Pure and Applied Mathematics, vol. 23, pp. 376-378, 1889. · JFM 21.0687.01
[12] G. Pólya, “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen,” Acta Mathematica, vol. 68, pp. 145-254, 1937. · Zbl 0017.23202 · doi:10.1007/BF02546665
[13] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972. · Zbl 0251.05107 · doi:10.1137/0201010
[14] N. Abel, “Beweis eines Ausdruckes, von welchem die Binomial-Formel ein einzelner Fall ist,” Journal für die Reine und Angewandte Mathematik, vol. 1, pp. 159-160, 1826. · ERAM 001.0019cj
[15] L. Székely, “Abel’s binomial theorem,” http://www.math.sc.edu/ szekely/abel.pdf.
[16] R. Diestel, Graph Theory, vol. 173, Springer, Berlin, Germany, 5rd edition, 2005. · Zbl 1077.05053 · doi:10.1002/jgt.20108
[17] M. J. Atallah and S. Fox, Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton, Fla, USA, 1998. · Zbl 0916.68001
[18] G. Kirchhoff, “Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird,” Annual Review of Physical Chemistry, vol. 72, pp. 497-508, 1847.
[19] Â. Mestre, “Generating connected and 2-edge connected graphs,” Journal of Graph Algorithms and Applications, vol. 13, no. 2, pp. 251-281, 2009. · Zbl 1180.68203 · doi:10.7155/jgaa.00187
[20] J. Cuntz, R. Meyer, and J. M. Rosenberg, Topological and Bivariant K-Theory, vol. 36, Birkhäuser, Basel, Switzerland, 2007. · Zbl 1177.58003 · doi:10.4171/OWR/2007/43
[21] C. Kassel, Quantum Groups, vol. 155, Springer, New York, NY, USA, 1995. · Zbl 0808.17003 · doi:10.1007/978-1-4612-0783-2
[22] J.-L. Loday, Cyclic Homology, vol. 301, Springer, Berlin, Germany, 1992. · Zbl 0780.18009
[23] M. Livernet, “A rigidity theorem for pre-Lie algebras,” Journal of Pure and Applied Algebra, vol. 207, no. 1, pp. 1-18, 2006. · Zbl 1134.17001 · doi:10.1016/j.jpaa.2005.10.014
[24] J. W. Moon, “Various proofs of Cayley’s formula for counting trees,” in A Seminar on Graph Theory, pp. 70-78, Holt, Rinehart & Winston, New York, NY, USA, 1967.
[25] K. Husimi, “Note on Mayers’ theory of cluster integrals,” The Journal of Chemical Physics, vol. 18, pp. 682-684, 1950. · doi:10.1063/1.1747725
[26] J. Mayer, “Equilibrium statistical mechanics,” in The International Encyclopedia of Physical Chemistry and Chemical Physics, Pergamon Press, Oxford, UK, 1968.
[27] P. Leroux, “Enumerative problems inspired by Mayer’s theory of cluster integrals,” Electronic Journal of Combinatorics, vol. 11, no. 1, research paper 32, p. 28, 2004. · Zbl 1054.05056
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.