4
$\begingroup$

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. Thanks for any help.

Define $d(i,j)$ to be the geodesic distance between two graph nodes $i$ and $j$. Say an $N$ node undirected graph is symmetric (this is my own definition) if:

$ \sum_{j=1}^N d(i,j) = c, \ \ \forall i$

Show that for symmetric, connected, non-trivial (i.e. not complete) graphs:

$ d(i,a) > d(i,b) \implies \sum_{j=1}^N d(i,j) d(a,j) \leq \sum_{j=1}^N d(i,j) d(b,j) $

To aid (possible) intuition here are a few graphs that satisfy the above condition. A circle graph:

$ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} $

Another example is a slightly incomplete star graph:

$ \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} $

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Note that if a graph is vertex-transitive, then it is `symmetric' by symmetry and we can wlog assume $i = 1$. The skeleton of the truncated icosidodecahedron is a counter-example to your conjecture, since the following plot (of $d(1, a)$ on the horizontal axis against $\sum\limits_{j=1}^N d(1,j) d(a,j)$ on the vertical axis) is not monotonically decreasing:

Counter-example to your conjecture

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the counter example, this is useful. Do you have any intuition of what sort of structure I could impose on graphs for this property to hold? $\endgroup$
    – Rob Richmond
    Commented Jun 27, 2014 at 21:52
  • $\begingroup$ Well, the counter-example shows that vertex-transitivity is not enough. My friend and colleague Gabriel Gendler proved that Kneser graphs and cycle graphs have your property, so maybe arc-transitivity suffices. en.wikipedia.org/wiki/Arc-transitive_graph $\endgroup$
    – Adam P. Goucher
    Commented Jun 28, 2014 at 11:06
  • $\begingroup$ Actually, arc-transitivity isn't enough, either; the Dyck graph lacks your property (and has just 32 vertices). $\endgroup$
    – Adam P. Goucher
    Commented Jun 28, 2014 at 11:17
  • $\begingroup$ The Dyck graph is particularly illustrative as it is one that I would have intuitively thought would have my property. Would you or Gabriel mind sharing a sketch of the proof for Kneser and cycle graphs? My cycle graph proof is really messy and doesn't point at all towards constraints I may be able to impose. $\endgroup$
    – Rob Richmond
    Commented Jun 30, 2014 at 18:48
  • $\begingroup$ I've been playing around a bit more with specific structures and using your Mathematica code to check the example graphs. Distance-transitive graphs may be a promising class en.wikipedia.org/wiki/Distance-transitive_graph . $\endgroup$
    – Rob Richmond
    Commented Jun 30, 2014 at 19:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .