2
$\begingroup$

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,

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?

$\endgroup$
1
  • $\begingroup$ I am essentially certain these results were computed by Brendan using his graph isomorphism package nauty. You could compute your graphs using the same tool, which you can download from his web site. I do not think there is any way to get what you need from his data. $\endgroup$ May 26, 2011 at 23:04

3 Answers 3

2
$\begingroup$

Do you want to count the graphs or find the graphs (by computer)?

If you actually want to find the graphs then it is pretty easy - you just want a graph with a partition of the vertex set into two parts - those with loops, and those without.

nauty allows you to impose an arbitrary (ordered) partition on the vertex set (i.e. a "colouring" in graph theory language) and compute a canonically labelled version of the graph that respects that partition.

Two graphs with loops are isomorphic if and only if

  • they have the same underlying simple graph, and
  • they have the same number of loops, and
  • the canonically labelled coloured graphs are identical.

The first property means you can just process each simple graph independently of the others..

$\endgroup$
1
$\begingroup$

My belief is somewhat contrary to Chris Godsil's. I would use McKay's list in the following way to determine isomorphism classes of graphs with loops.

Disclaimer: This is off the top of my head and unvetted, and may make assumptions that don't fit. I still think the method will be useful to you. To be more explicit, I assume McKay's list are complete of isomorphism types of unlabelled graphs with no multiple edges or loops, and that you desires something similar, excepting that you do allow single loops from nodes to themselves.

Let L be such a graph possibly with loops. For any such object L (or M, or N), let L' be the graph derived from L by removing all loops. Then L isomorphic to M implies L' is isomorphic to M', and if L is small enough, then L' is isomorphic to an item on McKay's list. There are at most 2^n graphs L that can produce the same L', so I would take an item from McKay's list, add loops to it in all the different ways, and (using some obvious shortcuts) determine which of these results were isomorphic.

The shortcuts would be easier if, along with such a graph, a list of vertex orbits under the automorpism group of the graph were provided. Then you could reduce the number of tests you have by assuming both graphs to be tested have the same number of loops in each orbit.

To illustrate, suppose I take the graph with n vertices and no edges. The vertex orbit is the same as the vertex set, so I know I will end up with at least n+1 different graphs when I add loops. It turns out I will have exactly n+1 different lopp graphs after testing for isomorphisms between some of the 2^n choose 2 possibilities. This work also covers the complementary graph, so I do not have to repeat it for the complete graph plus loops.

Gerhard "Ask Me About System Design" Paseman, 2011.05.26

$\endgroup$
1
$\begingroup$

This is A000666 .

Recent versions of nauty come with a tool vcolg that can make them. There is also another way, noted in the OEIS entry. Generate graphs on $n+1$ vertices. For one vertex $v$ from each orbit of the automorphism group, delete $v$ and add a loop to each vertex that $v$ used to be adjacent to.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.