Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If $G$ is a graph with distance function $d(x,y)$ between vertices, the transmission of a vertex $x \in v(G)$ is defined as $\sigma_{x}=\sum_{y \neq x}{d(x,y)}$. I want to know if there is a known characterization of graphs for which $\sigma_{x}$ is equal to the same number for all $x \in V(G)$.

Some easy examples: $K_{n},K_{p,p},C_{n}$. However, I found some non-regular examples as well.

UPDT: Those non-regular examples were a mistake in calculations - I still don't know if there are other, true ones.

UPDT2: As Gordon Royle pointed out, regular graphs of diameter 2 are transmission-unique; it can be easily shown that a transmission-unique graph of diameter 2 must be regular. He gave an example of diameter 3. Is there anything interesting to be said about such graphs of high diameter?

share|improve this question
1  
Do you have any non-vertex transitive examples? –  Gjergji Zaimi Nov 27 '12 at 2:38
3  
All regular graphs of diameter 2.... –  Gordon Royle Nov 27 '12 at 3:00
    
@Gordon: you mean strongly regular, I think. –  Dima Pasechnik Nov 27 '12 at 4:01
1  
If $k$-regular of diameter $2$, then transmission of each vertex is surely $k + 2 (n-k-1)$, regardless of strong regularity? –  Gordon Royle Nov 27 '12 at 4:36

2 Answers 2

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;
share|improve this answer
    
Gordon, thanks for the nice example. I had a feeling there had to be one! Did you find it in some "smart" way or by search? –  Felix Goldberg Nov 27 '12 at 11:15
    
This was a 3-second computer search. Or rather, I already had Brendan's program to generate the graphs and a program implementing Floyd's all-pairs-shortest paths algorithm. So all I had to write was something to check the row sums. Interestingly there are no non-regular examples on 10 vertices. I think Brendan's comment about cartesian product is correct, so there's no limit on diameter or non-regularity. It would still be interesting to see if these are special in any way; the example above has only 4 distinct eigenvalues, which may be relevant. –  Gordon Royle Nov 27 '12 at 14:18
    
I ran lots of random graphs but found none; probably my parameters were not good... –  Felix Goldberg Nov 27 '12 at 15:22
    
For those wondering what this graph looks like: Take 3 copies of the diamond graph and glue them together at the degree-2 vertices so as to form a triangle. –  Harry Altman Nov 27 '12 at 19:26
    
@gordon-royle: Try larger sizes for almost-regular graphs, you'll be able to go further. For example "geng -d6D7 12" only takes 30 sec. –  Brendan McKay Nov 27 '12 at 22:46

If I didn't get my wires crossed, the cartesian product of two transmission-regular graphs is also transmission-regular. This can be used to make examples of arbitrarily high diameter. I'll add a proof tomorrow if nobody finds a counterexample to my claim while I sleep.

ADDED: Let $G, H$ be connected graphs of order $m,n$, respectively. Then in the Cartesian product $G\times H$, we have $d_{G\times H}((u,x),(v,y)) = d_G(u,v)+d_H(x,y)$. From this it is easy to see that the transmission of $(u,x)$ is $n\sigma_u(G) + m\sigma_x(G)$. So $G\times H$ is transmission-regular iff both $G,H$ are.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.