Subgraph obtained by removing some edges with the largest possible number of orbits.

23 Views Asked by At

Suppose I have now a connected graph $G=(V,E)$. I care about the number of orbits of $E$ under the $\text{Aut}(G)$-action, say $a_G$. Note that if we deliberately eliminate some edges of $G$ cleverly, we may end up with some graph $G'=(V,E')$, where $E'=E\setminus \{\text{some edges of }G\}$, we may have the number $a_{G'} \leq a_{G}$. Sometimes strict less-than can happen.

Question: under what cases any $G'$ will lead to $a_{G'} \geq a_{G}$?

For example, if we have a complete graph $K_4$, then any $K_{4}'$ will have $a_{K_4'} \geq a_{K_4}=1$