# Maximum/minimum intersection of two graphs

I wonder if the following graph problems have been studied and have names.

Problem(s). Given two $n$-vertex unlabeled graphs $G_1$ and $G_2$, find their maximum/minimum edge intersection. That is find two labeled graphs $H_1 = ([n], E_1)$ and $H_2 = ([n],E_2)$ such that $H_1 \simeq G_1$, $H_2 \simeq G_2$, and $|E_1 \cap E_2|$ is maximized/minimized.

It would also be helpful to know if these problems have been studied for special classes of graphs, e.g. for trees.

• @Victor Let $G_1$ be a given graph on $n$ vertices and $G_2$ be the $n$ vertex cycle graph. Then $G_1$ has a Hamiltonian cycle if and only if the maximum edge intersection is $n$. – Michael Biro Nov 16 '16 at 13:01
• @MichaelBiro This shows how to solve the HAMILTONIAN CYCLE problem (HC), when you know how to solve the Maximum Common Edge Subgraph problem (MCES) (this what I meant by reduction from HC to MCES). But how can you solve MCES (with $G_1$ being a cycle) when you know how to solve HC? – Victor Nov 16 '16 at 14:50