[seqfan] A000081 & nonoverlapping circles(?)

[Jim Nastos]

On Fri, 13 Jun 2003, r.shepherd wrote:

> My misinterpretation of the comments in A000081 caused
> me to rediscover what are apparently called "penny graphs"
> according to a professor Jim Nastos contacted.

  Oh, gee... I'm no professor! A mere MSc student just
trying to get by in a complicated world.

> Currently, it looks like 1,1,2,4,10,25,...
> is the sequence for penny graphs (0,1,2,... unit circles with
> non-overlapping interiors).
> [My previous 9 was in error -- I missed at least 1 -- but
> we're fairly sure these are correct now.].

  For those familiar with graph intersection models, we are considering 
unit disc graphs in the plane such that the discs do not share any 
internal points.

  Now, if anyone happens to know of some good characterizations
of penny graphs, please let us know. For example, a complete
description of its minimal forbidden induced subgraphs would
allow me to generate a few more terms by generating all such
graphs. The only forbidden graph on 4 vertices is the K4, and 
there are nine minimal forbidden induced subgraphs of size 5. It is not 
hard to see that there are G(6) forbidden subgraphs (not necessarily 
minimal) of size 7, which are those graphs with a universal vertex. (where 
G(6) is the number of graphs, connected or otherwise,on 6 vertices) (a 
universal vertex is one that is adjacent to all other vertices.) These are 
due to the fact that the maximum degree can be 6.

  It would have been nice to have this massive number of forbidden graphs 
of size 7 end the list of minimal forbidden induced subgraphs, but 
(unfortunately) I can generate arbitrarily large forbidden graphs which 
are minimal with that property:

O---O---O-- ...  --O
 \ / \ / \  ...   / \
  O---O---O ...  O---0

  This is realizable with tangent pennies, but adding an edge to the 
left-most vertex with the right-most vertex make its infeasible.
  Because of this, for the sake of only generating the graphs up to N 
nodes, we only need the forbidden induced subgraphs of size up to N.

  Another property: for any two vertices {x,y} the common neighbourhood of 
them [ = N(x) intersect N(y) ] is at most 2. Furthermore, if x and y are 
adjacent and their common neighbourhood is of size 2, then these two 
vertices in their neighbourhoods are not adjacent.

> http://www.cs.ualberta.ca/~nastos/circles25.JPG

  Please note the "circles25.JPG" is case sensitive.

Thanks,
Jim Nastos