Skip to main content
added 1020 characters in body
Source Link
Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73

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 

ADDED: Some more comments and another example.

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;

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 

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 

ADDED: Some more comments and another example.

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;
Source Link
Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73

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