4
$\begingroup$

Take any undirected graph $G$. We say that $G$ is vertex-transitive iff for every vertices $v,w$ there is an automorphism on $G$ that maps $v$ to $w$. We say that $G$ is edge-transitive iff for every edge $e,f$ there is an automorphism on $G$ that maps $e$ to $f$. We say that $G$ is edge-flip-invariant iff for every edge with endpoints $v,w$ there is an automorphism on $G$ that maps $v$ to $w$ and maps $w$ to $v$.

Upon seeing these three kinds of symmetry, I had a curious question:

Question: What is the smallest $n$ such that there is a graph with $n$ vertices that is vertex-transitive but neither edge-transitive nor edge-flip-invariant?

The best I could think of was the snub cube (image from here):

the snub cube is a polyhedron with 6 unit squares and 32 unit equilateral triangles between them that can be inscribed in a sphere

It is clearly vertex-transitive, since every vertex is a vertex of a square. It is also not edge-transitive, since an edge between two triangles cannot be mapped by an automorphism to an edge next to a square. And it is not edge-flip-invariant, since no automorphism can flip an edge that is next to a triangle that is surrounded by triangles.

But is there a smaller graph with this property? I had found the snub cube by looking through 'nice' polyhedra (so that it is easy to verify vertex-transitivity), and I am unsure whether there is a better way of finding such graphs.

$\endgroup$
0

4 Answers 4

3
$\begingroup$

I think the following graph with $12$ vertices does the job, but I don't know if it is minimal.

It is basically a hexagonal (anti)prism with extra diagonals. Label the vertices $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, $A_6$ and $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$. The edges are $\{A_i, A_{i+1}\}$, $\{B_i, B_{i+1}\}$, $\{A_i, B_i\}$, $\{A_i, B_{i+1}\}$, $\{A_i, B_{i+3}\}$, where the indices are modulo $6$.

Here is a picture to be wrapped around a cylinder, connecting the left and right sides together.

enter image description here

I don't think this kind of construction can work using a prism with fewer sides without introducing a mirror symmetry which would make it edge-flip-invariant.

$\endgroup$
6
  • $\begingroup$ Thanks! I verified that your solution works! I tried antiprisms but didn't try crossing edges, so I missed such a graph. $\endgroup$
    – user21820
    Sep 29, 2020 at 8:46
  • $\begingroup$ @user21820 I think you can also use a truncated tetrahedron or cuboctahedron with some added diagonals to break the edge-flip-invariance (and edge transitivity in the latter case), but those are still 12 vertices. I think 11 vertices is impossible because it is prime and results in an 11-fold rotational symmetry which always leads to 11 mirror symmetries. I thought for a moment that a 10 vertex graph might be possible, but the only vaguely promising candidate is the Petersen graph, and that is edge-flip-invariant. $\endgroup$ Sep 29, 2020 at 9:33
  • $\begingroup$ @user21820 I think 9 is possible. Stack three triangular prisms together, and then identify the top face with the bottom face but with a twist, like a Moebius band. I might update my answer when I have more time to check it is correct. $\endgroup$ Sep 29, 2020 at 9:40
  • $\begingroup$ My idea for 9 vertices does not work, as it is edge-flip invariant. It contains a 9-cycle, and if you draw that as a regular nonagon, it has diagonals forming three regular triangles. This graph obviously has 9 mirror symmetries so you can flip every edge. $\endgroup$ Sep 29, 2020 at 11:18
  • $\begingroup$ @JaapScherphuis Can you see deleted posts? If so, I posted an idea to insert face diagonals into a truncated tatrahedron, but it turned out to be the icosahedron. Maybe other diagonals work better. $\endgroup$
    – M. Winter
    Sep 30, 2020 at 13:37
2
$\begingroup$

To flesh out the possible combinations of these three kinds of symmetry:

Note that edge-flip-invariance implies vertex transitivity for all connected graphs, because given any two vertices $U,V$ connected by a path, we can concatenate the automorphisms taking each vertex on this path to the next one and produce an automorphism sending $U$ to $V$.

All other 6 combinations are possible, however. Denoting vertex transitivity by $V$, edge-transitivity by $E$, and flip-transitivity by $F$:

(Note that a symmetric graph is just a graph satisfying all of $V, E,$ and $F$, because to send one arc to another, we send the associated edge to its target and flip if necessary.)

$\endgroup$
0
0
$\begingroup$

My original answer below was incorrect, that graph is edge-flip invariant. It is in fact a $3\times3$ torus, from which it is not hard to see that it has all the necessary automorphisms to be edge-flip invariant. I'm now quite convinced there is no such graph on fewer than $10$ vertices.

Old, incorrect answer:

I believe this graph on $9$ vertices is the smallest example:

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ I think this is the same as what I mentioned in a comment to my answer - stack three triangular prisms together, and then identify the top face with the bottom face but with a twist, like a Moebius band. $\endgroup$ Sep 29, 2020 at 10:12
  • $\begingroup$ It might very well be, I've been staring at graphs for so long my brain is completely fried; I must admit that I am not entirely sure it isn't edge-flip invariant. $\endgroup$
    – Servaes
    Sep 29, 2020 at 10:17
  • 2
    $\begingroup$ Actually, it is not the same. Yours has three twists, which is equivalent to no twists at all, so it is essentially just the 3x3 torus graph, and this is edge-flip invariant. Unfortunately my graph also does not work, as it too is edge-flip invariant. $\endgroup$ Sep 29, 2020 at 11:15
  • $\begingroup$ @JaapScherphuis I'll need some time to verify your statements. Anyway, this graph was the only graph on at most $9$ vertices that I could not exclude. So assuming I made no errors in my (long, manual) check, any such graph must have at least $10$ vertices. $\endgroup$
    – Servaes
    Sep 29, 2020 at 11:22
  • 1
    $\begingroup$ I used graphaffinity to draw it, and then moved around the vertices to simplify it. You could also use geogebra. $\endgroup$ Sep 29, 2020 at 11:26
0
$\begingroup$

This is a negative answer: I wanted to try the idea by Jaap on how to maybe get other 12-vertex examples. The idea was to add diagonals to the truncated tetrahedron or cuboctahedron. At least those instances that I tried failed, because both gave the edge-graph of the icoshedron.

truncated tetrahedron:

cuboctahedron:

Maybe we have to add body diagonals instead.

$\endgroup$
1
  • $\begingroup$ I am fairly certain that adding body-diagonals instead of these face diagonals will work, though I have not properly checked. In both cases there is essentially only one way to do that that isn't mirror symmetric. $\endgroup$ Sep 30, 2020 at 14:22

You must log in to answer this question.

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