# Claw-free cubic graphs...

Gordon Royle gordon at csse.uwa.edu.au
Fri May 30 07:47:59 CEST 2003

```I am trying to update and tidy up the entries related to claw-free cubic
graphs..

Labelled claw-free cubics can be counted - this is performed in the paper
"Counting Claw-Free Cubic Graphs" by Palmer, Read and Robinson (SIAM J.
Discrete Math, 16 65-73) available online at
http://www.cs.uga.edu/~rwr/publications/claw.pdf

The sequence they list, which is not yet in OEIS (I am happy to enter all
these once we get everything straight) is for all graphs, not just connected
ones; presumably I could unpack it to get the connected ones.

What *is* in the OEIS are various lists of *connected* labelled cubic
claw-free graphs, and in fact, refinements of these counts according to
connectivity equal to 1, 2 or 3 (the only possibilities for cubics).
The reference that is given is to a paper by "Chae, Palmer and Robinson"
which I cannot find anywhere  - does anyone know if it has appeared?

In fact, does anyone know where "Chae" even is - the link to his home page
(on the OEIS) does not work, and a quick google search failed to find him (I
didn't work too hard here).

The lists appearing on the OEIS are of labelled graphs, which superficially
gives one the impression of enormous scope and vastness... For example,
A057848 starts

0,1,60,2520,453600,59875200,13621608000,8009505504000,3123380227968000

for the numbers of connected claw-free cubic graphs on  2n=2,4,...18 nodes.

The numbers of *non-isomorphic* connected cubic claw-free graphs on the same
range are

0,1,1,1,1,3,3,5,11

which is a bit less exciting!

Gordon

```