# Enumerating subgraphs containing a given node

Given an undirected graph $G=(V,E)$ and a vertex $v\in V$, is there some algorithms to enumerate all induced subgraphs $G_s=(V_s,E_s)$, such that $v \in V_s$? It's preferred the algorithm doesn't enumerate duplicated subgraphs.

• Do the subgraphs have to be connected? If not, including vertex $v$ is almost no restriction. By duplicate, do you mean up to isomorphism, and should $s$ be regarded as a distinguished vertex, if so (e.g., are the paths $asb$ and $abs$ different)? Sep 7, 2015 at 15:35
• Thanks. A subgraph is connected, otherwise it's trivial. A subgraph duplicates another if they have the same vertices. Direction of paths are not considered Sep 7, 2015 at 15:39
• So you're looking for induced subgraphs? Please edit the question so all these points are clear without people needing to read the comments. Thanks. Sep 7, 2015 at 16:05
• In addition, please tell us in the question what you've tried and what you are stuck on. This looks like a straightforward programming question, so I'm having a hard time understanding what you find puzzling -- if you can help us understand that, it might help get you better answers. Have you looked at other questions tagged enumeration?
– D.W.
Sep 7, 2015 at 17:04