Strongly regular graph which is not edge transitive

Question

I am looking for a strongly regular graph which is not edge transitive. The implications in Wikipedia show that there is one, but I cannot find specific example. I would appreciate any hints in this direction. Thanks.

Answer 1

Searching through Mathematica's graph database gives a list of many examples...

{{"Chang", 1}, {"Chang", 2}, {"Chang", 3}, {"Paulus", {25, 1}},
 {"Paulus", {25, 2}}, {"Paulus", {25, 3}}, {"Paulus", {25, 4}}, 
 {"Paulus", {25, 5}}, {"Paulus", {25, 6}}, {"Paulus", {25, 7}}, 
 {"Paulus", {25, 8}}, {"Paulus", {25, 9}}, {"Paulus", {25, 10}}, 
 {"Paulus", {25, 11}}, {"Paulus", {25, 12}}, {"Paulus", {25, 13}}, 
 {"Paulus", {25, 14}}, {"Paulus", {26, 1}}, {"Paulus", {26, 2}}, 
 {"Paulus", {26, 3}}, {"Paulus", {26, 4}}, {"Paulus", {26, 5}}, 
 {"Paulus", {26, 6}}, {"Paulus", {26, 7}}, {"Paulus", {26, 8}}, 
 {"Paulus", {26, 9}}, {"Paulus", {26, 10}}, {"StronglyRegular", {{29, 14, 6, 7}, 1}},
 {"StronglyRegular", {{29, 14, 6, 7}, 2}}, {"StronglyRegular", {{29, 14, 6, 7}, 3}},
 {"StronglyRegular", {{29, 14, 6, 7}, 4}}, {"StronglyRegular", {{29, 14, 6, 7}, 5}},
 {"StronglyRegular", {{29, 14, 6, 7}, 6}}, {"StronglyRegular", {{29, 14, 6, 7}, 7}},
 {"StronglyRegular", {{29, 14, 6, 7}, 8}}, {"StronglyRegular", {{29, 14, 6, 7}, 9}},
 {"StronglyRegular", {{29, 14, 6, 7}, 10}}, {"StronglyRegular", {{29, 14, 6, 7}, 11}},
 {"StronglyRegular", {{29, 14, 6, 7}, 12}}, {"StronglyRegular", {{29, 14, 6, 7}, 13}},
 {"StronglyRegular", {{29, 14, 6, 7}, 14}}, {"StronglyRegular", {{29, 14, 6, 7}, 15}},
 {"StronglyRegular", {{29, 14, 6, 7}, 16}}, {"StronglyRegular", {{29, 14, 6, 7}, 17}},
 {"StronglyRegular", {{29, 14, 6, 7}, 18}}, {"StronglyRegular", {{29, 14, 6, 7}, 19}},
 {"StronglyRegular", {{29, 14, 6, 7}, 20}}, {"StronglyRegular", {{29, 14, 6, 7}, 21}},
 {"StronglyRegular", {{29, 14, 6, 7}, 22}}, {"StronglyRegular", {{29, 14, 6, 7}, 23}},
 {"StronglyRegular", {{29, 14, 6, 7}, 24}}, {"StronglyRegular", {{29, 14, 6, 7}, 25}},
 {"StronglyRegular", {{29, 14, 6, 7}, 26}}, {"StronglyRegular", {{29, 14, 6, 7}, 27}},
 {"StronglyRegular", {{29, 14, 6, 7}, 28}}, {"StronglyRegular", {{29, 14, 6, 7}, 29}},
 {"StronglyRegular", {{29, 14, 6, 7}, 30}}, {"StronglyRegular", {{29, 14, 6, 7}, 31}},
 {"StronglyRegular", {{29, 14, 6, 7}, 32}}, {"StronglyRegular", {{29, 14, 6, 7}, 33}},
 {"StronglyRegular", {{29, 14, 6, 7}, 34}}, {"StronglyRegular", {{29, 14, 6, 7}, 35}},
 {"StronglyRegular", {{29, 14, 6, 7}, 36}}, {"StronglyRegular", {{29, 14, 6, 7}, 37}},
 {"StronglyRegular", {{29, 14, 6, 7}, 38}}, {"StronglyRegular", {{29, 14, 6, 7}, 39}},
 {"StronglyRegular", {{29, 14, 6, 7}, 40}}}

...of which the easiest to point to are the three Chang graphs.

---

Let's look at one of these carefully to see why it's not edge transitive. To find the graph Mathematica calls {"Chang", 2}, we:

• Start with the line graph of $K_8$, a graph whose vertex set consists of pairs $\{i,j\} \subset \{1,2,3,4,5,6,7,8\}$ with an edge between pairs that have an intersection.
• Let $S$ be the set of four vertices $\{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}\}$.
• Perform a Seidel switch with respect to $S$: for all pairs of vertices $v \in S$, $w \notin S$, if $vw$ was an edge of the graph, delete it, and if it was not an edge, add it.

Intuitively, the "new" edges going across between $S$ and the complement of $S$ should be distinguishable from the "old" edges within the complement of $S$, so the result will not be edge-transitive. Indeed, that is true.

One way to see that is that each of the old edges is part of a clique of order $6$ such as the clique spanned by $\{\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{1,7\},\{1,8\}\}$. (In fact, each of the old edges is in two such cliques, which all have the form "spanned by all vertices outside $S$ containing element $k$" for some $k \in \{1, 2, \dots, 8\}$.) Meanwhile, one of the new edges, such as the edge connecting $\{1,2\}$ to $\{4,5\}$, is not part of any cliques of order $6$: their common neighbors are the pairs $\{i,j\}$ containing $4$ or $5$, disjoint from $\{1,2\}$, and not in $S$, which are $\{\{3, 5\}, \{3, 5\}, \{4, 6\}, \{4, 7\}, \{4, 8\}, \{5, 7\}, \{5, 8\}\}$ and which span two $K_3$'s.

The other two Chang graphs are obtained from the line graph of $K_8$ by performing a Seidel switch with respect to a different set: either $$S' = \{\{1,2\}, \{1,3\}, \{2,3\}, \{4,5\}, \{5,6\}, \{6,7\}, \{7,8\}, \{4,8\}\}$$ or $$S'' = \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,6\}, \{6,7\}, \{7,8\}, \{1,8\}\}.$$ Similar arguments show that they're not edge-transitive, but they're a bit harder to analyze because $S'$ and $S''$ are bigger than $S$.