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?

  • 5
    $\begingroup$ 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. $\endgroup$ – Austin Buchanan Oct 15 '13 at 22:09
  • $\begingroup$ yes. that is correct. should have realized from the last answer $\endgroup$ – 1.. Oct 15 '13 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.