20.71 (2022)

(J. Lauri). A card of a finite simple undirected graph $G$ of order $n = |V(G)|$ is an induced subgraph of order $n - 1$. Let $k$ be 2, 3, 4. For a connected graph $G$ with $k$ isomorphism types of cards, can $\text{Aut}(G)$ have more than $k$ orbits on the vertex set $V(G)$?
If a graph $G$ has $k$ isomorphism types of cards, then the group $\text{Aut}(G)$ of automorphisms of $G$ has obviously at least $k$ orbits on $V(G)$. It is known that if all cards are mutually isomorphic, then $\text{Aut}(G)$ is transitive on $V(G)$. Examples are known of graphs $G$ with 5 isomorphism types of cards for which $\text{Aut}(G)$ has 6 orbits on $V(G)$, and of graphs with 6 isomorphism types of cards for which $\text{Aut}(G)$ has 7 orbits on $V(G)$.