Partitions of Graphs V: Some Examples

This is the fifth in a series.  See the first here: Part I, and the previous here: Part IV.

In my last post I said what I mean by p(G), when G is a graph.  Namely, it is the number of partitions of n that are allowed by G.  (n is the number of nodes of G.  In fact through out this post G will always stand for a graph, and n for the number of nodes in G.)   This is something that I completely made up.  It is mostly just for fun, but I think that it might be interesting, and may even carry some significance.  Also, remember that q(G) is the number of partitions prohibited by G.  q(G)=p(n)-p(G).

Let’s get some examples under our belts.  We’ll compute p(G) (and/or q(G)) for some specific examples of G.

Complete Graphs

I said in the previous post that p(G) is always between 1 and p(n), i.e. .  So are there graphs with p(G)=p(n)?  Yes, in fact, there are.  the easiest example is probably the complete graph on n nodes.  A compete graph has an edge between every pair of nodes.  It is usually denote Kn (the particular number being substituted for n).

Below is K1

     o

and here is K2

     o-o

and K3

     o
     |\
     o-o

And here is how I will draw K4

     o-o
     |X|
     o-o

The X in the middle is supposed to be two edges that are crossed.  I don’t think that there is a good way to draw K5 in ASCII.  Here is a picture of K5 though:

Here the red dots are the nodes.  Where the edges of the star shape cross there are not nodes.

It is pretty easy to see that p(Kn)=p(n): Every partition is allowed, because in fact every coloring is good.  Said another way q(Kn)=0.

Edgeless Graphs

On the other extreme are the graphs with no edges at all:

     o o o o o

The only allowed partition of this graph is 1+1+1+1+1, since any coloring with two or more nodes the same color is bad.  Therefore:

     p( o o o o o )=1.

Similarly, p of any edgeless graph is 1.

Stars

We’ve seen graphs that allow all partitions of n, and graphs that allow only one, what about something in between?  The following graphs are called stars.  Here are the stars S4, S6 and S7:

       o
       |
       o
      / \
     o   o

       o
       |
     o-o-o
      / \
     o   o

     o   o
      \ /
     o-o-o
      / \
     o   o

Of course the biggest star I can draw in ASCII is S9:

     o o o
      \|/
     o-o-o
      /|\
     o o o

But you can have a star Sn for any whole number n (extra points for anyone who post a picture of S1,000,000).  Here is my claim: p(Sn)=n.  For example p(S5)=5, and here are the partitions that S9 allows:

5

4+1

3+1+1

2+1+1+1

1+1+1+1+1

It is pretty easy to see that these and only these partitions are allowed.  Here are the good colorings:

     o   o
      \ /
       o
      / \
     o   o

     o   o
      \ /
       o
      / \
     o   o

     o   o
      \ /
       o
      / \
     o   o

     o   o
      \ /
       o
      / \
     o   o

     o   o
      \ /
       o
      / \
     o   o

I’ll leave it to you to convince yourself that no other partitions are allowed.

Paths

We went a little overboard with the complete graphs.  Not nearly that many edges are needed for p(G) to be equal to p(n).  In fact what I consider to be the most important example I’ll talk about in this post is the path.  Below is a P3

     o-o-o

and a P4

     o-o-o-o

and for fun a P13

     o-o-o-o-o-o-o-o-o-o-o-o-o

It is not hard to see that paths allow every partiton of n.  Say n=13, and the partition you are interested in is 7+3+2+1, then to get a good coloring just color the first 7 nodes red, the next 3 blue, the next two green and the last one pink.

     o-o-o-o-o-o-o-o-o-o-o-o-o

Pretty slick huh?  For paths (and complete graphs) it seems more natural to talk about the function q.  Remember that q(G)=p(n)-p(G), so q(Pn)=0.  Paths, I think, are beautiful examples of graphs G with q(G)=0.  In my next post I will talk about some slick examples of graphs G with q(G)=1.

---

Possibly related posts: (automatically generated)

• Chasing Value: Journey to 201% APC, ISRG, WFC and more
• Corporate Press Release Theater: Dancing Without the Stars