<p>We have a theorem that, if the graph G is symmetric (both vertex and edge transitive) then G^p (by joining the vertices which are at the distance at most p in G) is also symmetric. See the reference ''Chromatic sets of power graphs and their application to resource
placement in multicomputer networks'' by N. Imani, H. Sarbazi-Azad, S.G. Akl, P. Moinzadeh;
Computers and Mathematics with Applications 58 (2009) 403–413.</p>

<p>But if you take Hypercube powers (Q_n)^p, the above question doesn't work out.</p>

CC BY-SA 3.0
2015-06-05T11:24:46.823Z
Are you sure? Can you give us an example where it fails?
Klaus Draeger
CC BY-SA 3.0
2015-06-06T06:25:42.557Z
Just a small note: Symmetric also requires that the graph be connected (This is also noted in the article). It seems that a simple induction on the distance suffices to prove the theorem, which is what is actually used in Theorem 2 of the paper you cite, with the automorphism also explicitly given.
chazisop
CC BY-SA 3.0
2015-06-12T19:29:38.663Z
Are you sure about it? Consider $(Q_n)^p$ for $p=2$. Let $v_0 = 0^n$: $v_1 = 10^{n-1}$ and  $v_2 = 110^{n-2}$. Is there mapping that maps the edge $(v_0,v_1)$ to $(v_0,v_2)$?
Igor Shinkar
<symmetry>
Number of common neighbors of any two adjacent vertices in a edge transitive graph is same or different?
user62619
# Number of common neighbors of any two adjacent vertices in a edge transitive graph is same or different?

(Asked by: username_0 on 2015-06-05)

We have a theorem that, if the graph G is symmetric (both vertex and edge transitive) then G^p (by joining the vertices which are at the distance at most p in G) is also symmetric. See the reference ''Chromatic sets of power graphs and their application to resource
placement in multicomputer networks'' by N. Imani, H. Sarbazi-Azad, S.G. Akl, P. Moinzadeh;
Computers and Mathematics with Applications 58 (2009) 403–413.

But if you take Hypercube powers (Q\_n)^p, the above question doesn't work out.

**Tags:** symmetry

> **Comments:**
> **username_1**: Are you sure? Can you give us an example where it fails?  
> **username_2**: Just a small note: Symmetric also requires that the graph be connected (This is also noted in the article). It seems that a simple induction on the distance suffices to prove the theorem, which is what is actually used in Theorem 2 of the paper you cite, with the automorphism also explicitly given.  
> **username_3**: Are you sure about it? Consider $(Q_n)^p$ for $p=2$. Let $v_0 = 0^n$: $v_1 = 10^{n-1}$ and  $v_2 = 110^{n-2}$. Is there mapping that maps the edge $(v_0,v_1)$ to $(v_0,v_2)$?  

---

## 0 answers

