The Counting of Isomorphism Classes of Mixed Graphs
DOI:
https://doi.org/10.61173/bcdta134Keywords:
-mixed graph isomorphism, Burnside’s lem-ma, coloringAbstract
Group theory and graph theory have important research value in mathematics today. Counting problems also play a decisive role in combinatorics. This paper introduces the number of isomorphism classes of mixed graphs with n vertices. The counting of them which using Burnside’s lemma is solved by converting the cases of edges and vertices to some colors.
References
[1] Armstrong, M. A. (Mark A. (1988). Groups and symmetry. Springer-Verlag.
[2] Babai, L. (2018). Groups, Graphs, Algorithms: The Graph Isomorphism Problem. http://www.people.cs.uchicago.edu/~laci/ papers/icm18-babai.pdf .
[3] Bell, M. V. (n.d.). P´olya’s enumeration theorem and its applications. https://helda.helsinki.fi/bitstream/ handle/10138/159032/GraduTiivistelma.pdf?sequence=3
[4] Bogart, K. P. (1991). An obvious proof of Burnside’s lemma. American Mathematical Monthly via American Mathematical Monthly.
[5] Dummit, D. S., & Foote, R. M. (2004). Abstract algebra (Third edition.). John Wiley and Sons, Inc.
[6] Fripertinger, H. (1993). Enumeration in musical theory (3.Aufl., Vol. 1). Institut für Elektronische Musik an der Hochschule für Musik und Darstellende Kunst.
[7] Hao, T. (2023). Burnside’s Lemma and Its Applications in Combinatorics Problems. Highlights in Science, Engineering and Technology, 47, 126–130. https://doi.org/10.54097/hset.v47i.8175
[8] Wright, E. M. (1981). Burnside’s lemma: A historical note. J. Comb. Theory B via J. Comb. Theory B.
[9] Yu, X., Liu, Z., Fang, Y., & Zhang, X. (2023). Learning to count isomorphisms with Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 4845–4853. https://doi.org/10.1609/aaai.v37i4.25610 [ 1 0 ] Z a b r o c k y, M . ( n . d . ) . C H A P T E R 6 : P O LYA ENUMERATION. Yorku. https://garsia.math.yorku. ca/~zabrocki/math4160f19/notes/ch6_polya.pdf
Downloads
Published
Issue
Section
License
Copyright (c) 2025 by the authors.
This work is licensed under a Creative Commons Attribution 4.0 International License.
