6
$\begingroup$

A graph $G$ is vertex transitive if for any two vertices $x$ and $y$ of $G$ there is an automorphism of $G$ that sends $x$ to $y$. Similarly, $G$ is edge transitive if for any two edges $e$ and $f$ of $G$ there is an automorphism of $G$ that sends $e$ to $f$.

A necessary condition for vertex transitivity is that $G$ be regular. If $G$ is regular and edge transitive but not vertex transitive, it is called semi-symmetric.

  1. Is there a name for graphs that are vertex transitive but not edge transitive? Is there a characterization for these types of graphs?

  2. Sometimes a graph can be as close as possible to being edge transitive without actually having that quality, ie. the edge automorphism group of $G$ (the automorphism group of the line graph of $G$) has exactly two orbits. If this is the case does it imply anything interesting about $G$ (besides that there are essentially two "types" of edges in $G$)? I'm particularly interested in the case where $G$ is vertex transitive.

Thank you.

$\endgroup$
6
$\begingroup$
  1. I do not think there is a name or a characterization for these graphs. An edge-transitive graph that is not bipartite is vertex transitive and there may well be other results of this flavour.

  2. I do not recall seeing any study of vertex-transitive graphs with exactly two orbits on edges. In studying group actions on graphs, arc-transitivity tends to be more natural than edge transitivity (or at least easier to deal with). Note that it is actually not easy to find useful things to say about graphs that are vertex and edge transitive, and weakening the transitivity assumptions will only make things harder.

$\endgroup$
  • $\begingroup$ Before we start questioning the characterization, do there exist any such graphs? Can you give me an example please? $\endgroup$ – Siddhartha Nov 26 '17 at 15:39
  • $\begingroup$ If you're asking for graphs that are vertex-transitive but not edge-transitive, the complement of any cycle with seven or more vertices will do. Or google Most vertex transitive graphs will not be edge transitive. $\endgroup$ – Chris Godsil Nov 26 '17 at 22:53
2
$\begingroup$

The graph corresponding to a triangular prism is vertex-transitive but not edge-transitive. More generally, two copies $G,G'$ of the complete graph $K_n$ for $n\geq 3$ that are linked by $n$ edges (one edge between $v_i$ and $v_i'$ for each $i$) is vertex-transitive but not edge-transitive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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