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 throughout 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.
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
and here is K2
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.
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.
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 S5 allows:
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.
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
and a P4
and for fun a P13
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.
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.