Partitions of Graphs VIII: The case of 11 (and 17)

This is the eighth in a series, the first being here: Part I and the previous here: Part 7.

We have shown that there are no Q1 graphs with n=5 nodes or with n=7 nodes.  Also, in the case of n=9, it apears that the reason there are Q1 graphs is that 9 is divisible by 3 (3+3+3 being the Q1 partition).  It is tempting to guess that for n=11 there are no Q1 graphs.  This however is not the case.  Here is one

                o
                |
    o-o-o-o-o-o-o-o-o
                |
                o

The prohibited partition is 4+4+3.  The easiest way to see this is to show that any partition which has a 1, 2, or anything larger than a 4 as a summand is allowed, so the only prohibited partitions have only 4s and 3s as summands.  But there is only one way to represent 11 as a sum of 4s and 3s, namely 4+4+3.  The same logic works to show that this 17 node graph is also Q1:

                            o
                            |
    o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
                            |
                            o

But adding another six nodes to the tail gives this graph which is not Q1:

                                        o
                                        |
    o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
                                        |
                                        o

Since there are two ways of representing 23 as a sum of 4s and 3s, namely 4+4+4+4+4+3 and 4+4+3+3+3+3+3.

Advertisements
This entry was posted in graphs and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s