# On the subgraph isomorphism problem

The subgraph isomorphism problem problem is to determine given $G$ and $H$ whether $G$ is a subgraph of $H$.

Let $G$ and $H$ be regular graphs with degree of $H$ greater than degree of $G$.

Does the subgraph isomorphism problem remain NP-complete for the following case:

$1.$ Girth of $G$ and $H$ are fixed, say $girth=3$ or a fixed $h$?

How large should a fixed $k$-diameter $d_H$-regular graph $H$ be for it to have a fixed $k$-diameter $d_G$-regular subgraph $G$ of vertex count $n_G$ when both have the same girth?

• Subgraph isomorphism remains NP-complete when G is complete (i.e., diameter=1). The graph H constructed in the standard reduction from 3SAT to CLIQUE has diameter 2. You should be able to add dummy vertices and edges to any graph H so that it is regular and its clique number is preserved. – Austin Buchanan Oct 15 '13 at 22:09
• yes. that is correct. should have realized from the last answer – 1.. Oct 15 '13 at 23:10