Primitive graphs

A primitive graph is one whose automorphism group acts primitively on the vertices: that is, the group is transitive on the vertices, and there is no non-trivial equivalence relation which it preserves.

This post is not about why primitive graphs are important, but what is special about them.

A non-null primitive graph is connected (else the connected components would be the classes of an invariant equivalence relation). If it has more than two vertices, then it is not bipartite. But are there any other, more local properties that primitive graphs have but general (or even vertex-transitive) graphs do not?

For a start, every (finite) graph is an induced subgraph in some primitive graph. (This is an exercise for you, gentle reader; you may like to think about intersection graphs.) So entirely local property can single out primitive graphs.

This is the best that I can do at present.

Theorem A primitive graph with chromatic number r > 1 cannot have the complete graph on r+1 vertices minus an edge as an induced subgraph.

Note that this is not true for transitive graphs, as the complete r-partite graph shows.

To see this, suppose that the vertices 1,2,…,r+1 carry such a subgraph of a primitive graph Γ with chromatic number r, where the edge {r,r+1} is missing. Take a fixed colouring c with r colours. The vertices {1,…r} carry a complete subgraph, and so lie in distinct colour classes. So do the vertices {1,…r−1,r+1}. So r and r+1 lie in the same colour class. The same would be true for any image of this subgraph under an automorphism g.

Now let Δ be the graph whose edge set is the orbit under G of the pair {r,r+1}. Every edge of Δ is contained within a colour class of c; so Δ cannot be connected, a contradiction (since it is also a non-null primitive graph).

My question is:

Question Have you seen any similar results about primitive graphs?


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , , . Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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