Polya's Enumeration Theorem: Number of colorings of n-gons and non isomorphic graphs,
2010 (English)Independent thesis Advanced level (degree of Master (One Year)), 15 credits / 22,5 HE credits
Student thesis
Abstract [en]
Polya’s theorem can be used to enumerate objects under permutation groups. Using grouptheory, combinatorics and some examples, Polya’s theorem and Burnside’s lemma arederived. The examples used are a square, pentagon, hexagon and heptagon under theirrespective dihedral groups. Generalization using more permutations and applications tograph theory.Using Polya’s Enumeration theorem, Harary and Palmer [5] give a function whichgives the number of unlabeled graphs n vertices and m edges. We present their work andthe necessary background knowledge.
Place, publisher, year, edition, pages
2010. , p. 45
Keywords [en]
Generating function; Cycle index; Euler’s totient function; Unlabeled graph; Cycle structure; Non-isomorphic graph.
Identifiers
URN: urn:nbn:se:lnu:diva-6199OAI: oai:DiVA.org:lnu-6199DiVA, id: diva2:324594
Presentation
2010-06-14, B2034, Linnaeus University, 16:11 (English)
Uppsok
Physics, Chemistry, Mathematics
Supervisors
Examiners
2010-06-162010-06-152010-06-16Bibliographically approved