MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 1020 characters in body

Here's a non-regular one:

Graph 1, order 9.
0 : 3 6 7;
1 : 4 6 8;
2 : 5 7 8;
3 : 0 6 7;
4 : 1 6 8;
5 : 2 7 8;
6 : 0 1 3 4;
7 : 0 2 3 5;
8 : 1 2 4 5;


Now the list of pairwise distances

0 2 2 1 2 2 1 1 3
2 0 2 2 1 2 1 3 1
2 2 0 2 2 1 3 1 1
1 2 2 0 2 2 1 1 3
2 1 2 2 0 2 1 3 1
2 2 1 2 2 0 3 1 1
1 1 3 1 1 3 0 2 2
1 3 1 1 3 1 2 0 2
3 1 1 3 1 1 2 2 0


Clearly one way for a regular graph to have this unique-transmission-value property is if every vertex has the same number of vertices at each distance from it. Vertex-transitive graphs, distance-regular graphs, the regular graphs of diameter 2 etc all fall into this category. You could easily fool around with graphs of higher diameter and make the girth high enough to force this to happen. These graphs are likely to be impossible to characterise any more precisely.

So the non-regular ones are perhaps more interesting. But here again, we have numerous examples due to Brendan's cartesian product example, so its not clear where to go. But it looks ugly. Here's another example, on 11 vertices, with not much obvious structure.

Graph 1, order 11.
0 : 4 7 8 9;
1 : 5 6 7 10;
2 : 5 8 9;
3 : 6 8 9;
4 : 0 7 8 9;
5 : 1 2 6 10;
6 : 1 3 5 10;
7 : 0 1 4 10;
8 : 0 2 3 4;
9 : 0 2 3 4;
10 : 1 5 6 7;

1

Here's a non-regular one:

Graph 1, order 9.
0 : 3 6 7;
1 : 4 6 8;
2 : 5 7 8;
3 : 0 6 7;
4 : 1 6 8;
5 : 2 7 8;
6 : 0 1 3 4;
7 : 0 2 3 5;
8 : 1 2 4 5;


Now the list of pairwise distances

0 2 2 1 2 2 1 1 3
2 0 2 2 1 2 1 3 1
2 2 0 2 2 1 3 1 1
1 2 2 0 2 2 1 1 3
2 1 2 2 0 2 1 3 1
2 2 1 2 2 0 3 1 1
1 1 3 1 1 3 0 2 2
1 3 1 1 3 1 2 0 2
3 1 1 3 1 1 2 2 0