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

<p>Let $G$ and $H$ be regular graphs with degree of $H$ greater than degree of $G$.</p>

<p>Does the subgraph isomorphism problem remain NP-complete for the following case:</p>

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

<p>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?</p>

CC BY-SA 3.0
2013-10-15T22:09:10.263Z
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
CC BY-SA 3.0
2013-10-15T23:10:57.503Z
yes. that is correct. should have realized from the last answer
Turbo
<graph-theory><graph-isomorphism>
On the subgraph isomorphism problem
Turbo
# On the subgraph isomorphism problem

(Asked by: username_0 on 2013-10-15)

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?

**Tags:** graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: 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.  
> **username_0**: yes. that is correct. should have realized from the last answer  

---

## 0 answers

