# [seqfan] Re: partitions of a circle

Neil Sloane njasloane at gmail.com
Fri May 11 03:45:18 CEST 2012

```Yes, I did not mean to imply that what I wrote
down was a complete definition of the problem,
far from it. But it does supply a framework for attacking the problem.
We have a graph with 2 kinds of nodes (boundary nodes P_1, ..., P_b and
internal nodes Q_1, ..., Q_i),
and two kinds of edges (boundary edges E_1, ..., E_b, which form a
cycle together with the boundary nodes, and internal edges F_1, ..., F_e).
Then we have a number of conditions to satisfy:
|edges|-|nodes|+1 =b+e-b-i+1=e-i+1= n
every node has degree >= 3
there is at most one internal edge between any two nodes
the graph must be planar and connected
there are no self-loops
and probably other conditions

Neil

On Thu, May 10, 2012 at 8:00 PM, Andrew Weimholt
<andrew.weimholt at gmail.com>wrote:

> correction...
> The first figure would be n=3, not n=2
>
> Also, in the second figure, I should've
> included another line segment and made it n=5
> to illustrate that a "bad" edge can arise even
> without any interior points with valence < 3.
>
>        Q
>       /|\
>  P---Q-Q-Q
>       \|/
>        Q
>
> Andrew
>
> On 5/10/12, Andrew Weimholt <andrew.weimholt at gmail.com> wrote:
> > On 5/10/12, Neil Sloane <njasloane at gmail.com> wrote:
> >>
> >> I could write out a set of rules, I think. We describe
> >> the picture by giving a list of points P_1, P_2, ... going around the
> >> boundary, together with interior points Q_1, Q_2, ...
> >> Then we just say what the lines are joining the points.
> >>
> >
> > The rules need a little more fleshing out...
> >
> > For example,
> > 1. Every edge must separate two distinct regions.
> > 2. Every interior vertex (Q_1, Q_2, ...) must have valence >= 3
> >
> > otherwise we could have figures such as the following
> > [view in a fixed-width font]:
> >
> >         Q
> >        / \
> >   P---Q---Q---P
> >
> >   (for n=2)
> >
> > OR      Q
> >        /|\
> >   P---Q-Q-Q
> >        \ /
> >         Q
> >
> >   (for n=4)
> >   Note: the P-Q edge borders the same region on both sides.
> >
> > Andrew
> >
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

--
Dear Friends, I will soon be retiring from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA