Intereting Posts

Combinatorial Proof Question
Difference between metric and norm made concrete: The case of Euclid
The Language of the Set Theory (with ZF) and their ability to express all mathematics
Compute center, axes and rotation from equation of ellipse
Verifying Ito isometry for simple stochastic processes
Connectedness of a regular graph and the multiplicity of its eigenvalue
Decomposition into partial fractions of an inverse of a generic polynomial with three distinct roots.
Smallest number with specific number of divisors
Is there any branch of Mathematics which has no applications in any other field or in real world?
How many squares contains paint
A linear operator commuting with all such operators is a scalar multiple of the identity.
Circle on sphere
Is there a bijection between $(0,1)$ and $\mathbb{R}$ that preserves rationality?
Is there a finite abelian group $G$ such that $\textrm{Aut}(G)$ is abelian but $G$ is not cyclic?
Deriving the formula for the $n^{th}$ tetrahedral number

Brendan McKay has already done the work for finding all non-isomorphic graphs of n variables that can be found here (under Simple Graphs): http://cs.anu.edu.au/~bdm/data/graphs.html

I believe this was done using polya enumeration, which I understand the basics of. I would like to expand on this, and allow self loops in these graphs. So, i’d like to find all non-ismorphic graphs of n variables, including self loops. This will be directly used for another part of my code and provide a massive optimization. I’m just not quite sure how to go about it.

To be clear, Brendan Mckay’s files give all non ismorphic graphs, ie in edge notation,

- Ways of merging two incomparable sorted lists of elements keeping their relative ordering
- Multinomial Theorem Example Questions
- Odd and even numbers in Pascal's triangle-Sierpinski's triangle
- Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$
- Determinant of a generalized Pascal matrix
- Expected number of coin tosses needed until all coins show heads

1-2 1-3

is a graph with an edge between vertex 1 and 2, and 1 and 3. I want this list to also include self loops, ie:

1-2 1-3 1-1

or

1-2 1-3 1-1 2-2

I want the minimum number of graphs, so all non-ismorphic ones. How can I go about finding them, hopefully using the data Brendan McKay has available for simple graphs?

- Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$
- A mouse leaping along the square tile
- In how many ways can you select one of the two but not both?
- No cycle containing edges $e$ and $g$ implies there is a vertex $u$ so that every path sharing one end with $e$ and another with $g$ contains $u$
- How many nodes are there in a 5-regular planar graph with diameter 2?
- Integral identity graphs — smallest example
- Matching Hats AND Coats Problem
- Non-probabilistic proofs of a binomial coefficient identity from a probability question
- How to verify a shortest path tree with O(V+E) running time by giving node's predecessor and shortest distance
- “8 Dice arranged as a Cube” Face-Sum Equals 14 Problem

This can indeed be done with the Polya Enumeration Theorem. There is a very simple yet powerful observation that can be made here: if we have the cycle index of the edge permutation group induced by the action of the symmetric group on the vertices, the cycle index of the edge permutation group including self-loops can be obtained by multiplying the factorizations into disjoint cycles of the edge permutation and the original vertex permutation and sum these contributions for all vertex permutations. (Of course we work directly with the cycle index of the symmetric group which is much more efficient than iterating over all permutations.) But the cycle index of the edge permutation group is not difficult to compute, the code can be found at this MSE Link.

This gives the following cycle indices for the enumeration of graphs that may have self-loops: for $n=2$ we have

$$1/2\,{a_{{1}}}^{3}+1/2\,a_{{1}}a_{{2}},$$

for $n=3$ we get

$$1/6\,{a_{{1}}}^{6}+1/2\,{a_{{1}}}^{2}{a_{{2}}}^{2}+1/3\,{a_{{3}}}^{2},$$

and finally for $n=4$ we obtain

$$1/24\,{a_{{1}}}^{10}+1/4\,{a_{{1}}}^{4}{a_{{2}}}^{3}+1/3\,{a_{{3}}}^{3}a_{{1}}+1

/8\,{a_{{1}}}^{2}{a_{{2}}}^{4}+1/4\,a_{{2}}{a_{{4}}}^{2}.$$

As an example we substitute $1+z$ into the cycle index for $n=3$ to get

$${z}^{6}+2\,{z}^{5}+4\,{z}^{4}+6\,{z}^{3}+4\,{z}^{2}+2\,z+1.$$

There are indeed two graphs on three vertices with $1$ edge including loops, namely a single edge or a single loop. Similarly there are four graphs with $2$ edges, namely two loops, two edges, an edge with a loop on one end and an edge that is opposed to a vertex with a loop on it. Furthermore the six graphs with three edges are: a triangle with no loops, a fork with a loop on the handle, a fork with a loop on one of its ends, a line segment with two loops at either end, a line segment with a loop on one end and a loop not incident on the line segment, and finally, three loops. It goes on like this.

These cycle indices produce the following total counts of non-isomorphic undirected graphs with possible self-loops present:

1 6 20 90 544 5096 79264 2208612 113743760 10926227136 1956363435360 652335084592096 405402273420996800 470568642161119963904 1023063423471189431054720 4178849203082023236058229792 32168008290073542372004082199424 468053896898117580623237189908861696 12908865186281154904787051023018388368640 676599895346467962508983189158040730734206464 67557268911383303274368343026941404659790140175872 12878644470123443279570180725329554086442149175832124416 4696891990987444795146988875290693218960182452250871238964224 3283275444870880220030739747435965751837707129958501790119044590592 4406671511641658245922265014648856899986657018190959680004287879813376000 11374011362523188765310166602160674880959112891073505609667787021125321629659136

This sequence of values points us to OEIS A000666 where a large amount of additional material can be found.

For those who are curious to see the details, here is the Maple code to compute these values:

with(numtheory); with(group): with(combinat): pet_cycleind_vrec := proc(n) local p, s; option remember; if n=0 then return 1; fi; expand(1/n*add(a[l]*pet_cycleind_vrec(n-l), l=1..n)); end; pet_flatten_term := proc(varp) local terml, d, cf, v; terml := []; cf := varp; for v in indets(varp) do d := degree(varp, v); terml := [op(terml), seq(v, k=1..d)]; cf := cf/v^d; od; [cf, terml]; end; pet_cycleind_edg := proc(n) option remember; local s, t, res, cycs, l1, l2, flat, u, v; if n=0 then return 1; fi; s := 0: for t in pet_cycleind_vrec(n) do flat := pet_flatten_term(t); cycs := flat[2]; res := 1; for u to nops(cycs) do for v from u+1 to nops(cycs) do l1 := op(1, cycs[u]); l2 := op(1, cycs[v]); res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2)); od; od; for u to nops(cycs) do l1 := op(1, cycs[u]); if type(l1, odd) then # a[l1]^(1/2*l1*(l1-1)/l1); res := res*a[l1]^(1/2*(l1-1)); else # a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1) res := res*a[l1/2]*a[l1]^(1/2*(l1-2)); fi; od; s := s + res*t; od; s; end; pet_varinto_cind := proc(poly, ind) local subs1, subs2, polyvars, indvars, v, pot, res; res := ind; polyvars := indets(poly); indvars := indets(ind); for v in indvars do pot := op(1, v); subs1 := [seq(polyvars[k]=polyvars[k]^pot, k=1..nops(polyvars))]; subs2 := [v=subs(subs1, poly)]; res := subs(subs2, res); od; res; end; v := proc(n) option remember; local p, k, gf; p := q1+q2; gf := expand(pet_varinto_cind(p, pet_cycleind_edg(n))); subs({q1=1, q2=1}, gf); end;

The quick-and-dirty method would be to add self-loops in all possible ways for each graph, and check which of them are isomorphic.

A more sophisticated way will first calculate the automorphism group of the graph, and use that data to solve your problem. That can save a lot of time since for most graphs, the automorphism group is trivial.

McKay’s library can check whether two graphs are isomorphic, and I think it also calculates the automorphism group (at least in some sense). At the very least, you should be able to use the quick-and-dirty method only for graphs with non-trivial automorphism group.

- Given point and tangent line
- Is the derivative of an integral always continuous?
- programming language with HALTS keyword
- Solve the following equation for x and y:
- Elementary proof of the fact that any orientable 3-manifold is parallelizable
- How will the limit $\lim \sin(A^{n})$ behave for $|A| > 1$?
- Representation of the dual of $C_b(X)$?
- Calculate the series expansion at $x=0$ of the integral $\int \frac{xy\arctan(xy)}{1-xy}dx$
- Holomorphic Poincaré conjecture
- Where does one use holomorphicity in the proof of Goursat's theorem?
- Some questions concerning the size of proper classes in ZFC
- Intuition for complex eigenvalues
- Prove that any two consecutive terms of the Fibonacci sequence are relatively prime
- Fodor's lemma on singular cardinals
- Why Rational Root Theorem only works with integers