Let $G,H$ be two simple graphs. Let's call a subgraph of $H$ that is isomorphic to $G$ a $G$-subgraph. Consider the following construction:
Construction: Let $\mathcal G=\mathcal G(G,H)$ be a graph defined as follows
- the vertices of $\mathcal G$ are the $G$-subgraphs of $H$.
- two such $G$-subgraphs $G_1,G_2\subseteq H$ are connected by an edge in $\mathcal G$, if and only if there is no $G$-subgraphs in the union $G_1\cup G_2\subseteq H$ other than $G_1$ and $G_2$.
We might set $H=K_n$ for simplicity. At least this is the case I mostly dealt with.
Question: For what graphs $G,H$ is $\mathcal G(G,H)$ highly symmetric, e.g. edge-transitive, or even arc-transitive?
Note that it is not hard to make $\mathcal G(G,H)$ just vertex-transitive, e.g. $H=K_n$ already ensures this.
Generalizations (that might make it easier)
The question might be generalized as follows, and I would be still very interested in examples: $G,H$ might be directed graphs, or multi graphs. This changes what is meant by beeing "isomorphic" to $G$.
Some examples and further thoughts
- Trivial cases include $G=H$ or when $G$ has not edges.
- Let $G$ be the $n$-cycle and $H=K_n$. This will give you a very complicated graph related to the edge-graph of the traveling-salesman-polytope. It is usually not edge-transitive.
- Consider Hamiltonian cycles in the cube, i.e. $G=C_8$ and $H=Q_3$. Then $\mathcal G$ is the octahedral graph, hence arc-transitive.
- Let $G$ be a the graph consisting of $k$ disjoint edges, and $H$ the graph consisting of $n\ge k$ disjoint edges. Then $\mathcal G$ is the Johnson graph $J(n,k)$, hence arc-transitive.
- I have the feeling that $G$ must be connected, very symmetric itself (e.g. arc-transitive), with a very symmetric complement (if $H=K_n$), und should use $\approx$ half of the edges of $H$. These are just feelings, nothing concrete here. I considered the Petersen graph in $H=K_{10}$, but this seems not to give edge-transitivity.
