Using OEIS...

[Gordon Royle]

A real-life story of using OEIS..

I am currently working on a problem where graphs that are obtained
from smaller graphs by replacing a vertex by a clique (and adjoining the 
neighbours of the vertex to each element of the clique) need not be 
considered. In other words, I just need the "reduced" graphs where 
no two adjacent vertices u and v have the property that 
N(u) - {v} = N(v) - {u}.

So I calculated these (connected) graphs on up to 10 vertices or so, and 
got the numbers

3,11,61,507,7442,197772,9808209

As usual, bung them into OEIS and up comes the sequence A004108 which is
connected graphs without endpoints - in other words, graphs without 
vertices of degree 1.

So, what is the connection between these "reduced" graphs and having
minimum degree two (they are not the same set of graphs)...

It turns out that there is a simple, but cute, bijection between the
two classes of graphs that might make a nice little student exercise...

I will leave it as a puzzle for anyone interested in some gentle mental
exercise.. .. and I'll add the answer in a few days as a comment to A004108.

All the best

Gordon

PS I am still looking for someone who can tell me what a "basic circuit
of nullity n" is, and whether it really is just a 3-connected cubic
graph.....


-- 
Dr. Gordon F Royle, http://www.csse.uwa.edu.au/~gordon, gordon at csse.uwa.edu.au
--