Location parameters and twin vertices

It is a pleasant experience when two previous interests suddenly reappear and combine to give something new. This happened to me yesterday, and to add to the pleasure, the two previous interests were things I had first worked on with former students: location parameters and twin vertices in graphs.

Location parameters

If you are lost, you look for landmarks, and find your position by using them. Location parameters describe this procedure in graphs.

Let Γ be a graph. A set S of vertices is called a metric resolving set if all vertices can be uniquely identified from knowledge of the list of their distances from vertices in S; in other words, if d(v,s) = d(w,s) for all vertices s in S, then v = w. The metric dimension of Γ is the size of the smallest metric resolving set.

This parameter and other similar ones cropped up many times and were given many different names; this resulted in a large amount of duplication of work, since one researcher had no easy way of finding out what others had done. This prompted my former student Robert Bailey to suggest to me that we should try to write a definitive survey about this, pulling together all the different names. We did, and it is now one of my most cited papers, in the Bulletin of the London Mathematical Society in 2011.

There are other similar measures. For example, if we replace “distances” by “adjacencies” in the definition (i.e. require that a vertex is determined by the set of its neighbours in S) we get adjacency resolving sets and adjacency dimension. (I always felt that this was a much more natural concept in a graph than the metric versions, but it has not received as much attention.)

An alternative version is to use symmetry as our guide: S is a base if, for any two distinct vertices v and w, there is no automorphism of Γ moving v to w and fixing all vertices in S. The size of the smallest base is, of course, the base size.

Since any adjacency resolving set is a metric resolving set, and any metric resolving set is a base, the sequence (base size, adjacency dimension, metric dimension) is non-decreasing. The gaps can be arbitrarily large: for example, a long path has metric dimension 1 but large adjacency dimension, while a large random graph has base size 1 but large metric dimension.

Twin vertices

I came across these and their significance when I was working with my former student Colva Roney-Dougal on generation of groups. We were looking at the generating graph, whose vertex set is the group, two vertices joined if they generate the group. We constructed the generating graph of the alternating group A₅, and idly wondered what its automorphism group was, expecting it to be not too far from the group A₅ itself. To our shock, the computer told us that the number of automorphisms was 23482733690880.

It turns out that most of this is explained by twin vertices. Two vertices v and w of a graph Γ are twins if they have the same neighbours apart from one another. So there are two kinds of twins: closed twins, where v and w are joined, and open twins, where they are not. Fortunately it turns out that a vertex cannot have both a closed twin and an open twin. So being equal or twins is an equivalence relation on the vertex set, and all pairs of vertices in a non-singleton equivalence class are the same kind of twins.

If v and w are twins, then the transposition swapping these two vertices and fixing everything else is a graph automorphism, which tells nothing about the graph except that the two vertices are twins. So the automorphism group contains the direct product of symmetric groups on the non-singleton twin classes. Now in the generating graph of A₅, an element of order 3 or 5 is twin to all its non-identity powers; so the automorphism group contains (S₂)¹⁰×(S₄)⁶, and all these automorphisms should be regarded as junk.

The argument shows that for graphs defined on groups (generating graph, commuting graph, power graph, etc.), there are many pairs of twins. I found that twin reduction (where we successively identify pairs of twins until none remain) was a valuable tool for investigating these graphs.

Combining

In the course of straightening out the proof of a theorem, I noticed the relation between location parameters and twins. Here is a clean and simple result showing how it works.

Theorem Let Γ be a graph in which every vertex has a twin. Then the base size, metric dimension, and adjacency dimension of Γ are all equal; the common value is the number of vertices minus the number of twin classes.

Here is the proof. Let n and r be the numbers of vertices and twin classes in a graph satisfying the hypothesis.

First we show that the base size is at least n−r. Suppose that S is a set of size smaller than this. Then there must be a twin class containing two vertices outside S. We can swap these two without affecting the rest of the graph. So S is not a base.

Then we show that the adjacency dimension is at most n−r. Take a set S containing all but one vertex from each twin class. Then S has size n−r. We claim that it is an adjacency resolving set. Two vertices outside S are not twins, and so differ in their adjacencies to some vertex, say w. But then they differ in their adjacencies to every vertex in the twin class of w, and at least one of these lies in S.

Thus the non-decreasing sequence (base size, metric dimension, adjacency dimension) we met earlier is bounded above and below by n−r, and the theorem is proved.

There is a lot more that can be said. For example, suppose that Γ has a unique universal vertex (joined to all others), and all other vertices are twins. Then the three location parameters of Γ are all equal. I do not know if there is a general theorem summing all this up, but I think it is a technique rather than a theorem. Also, similar things can be done for relational structures other than graphs.

Anyway, I recommend the study of location parameters of graphs defined on groups to those interested in the subject.