1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to induce a minimal subgraph

  1. Apr 6, 2012 #1
    I have a undirected graph G and a subset S of nodes from G. If I only do vertex-induced subgraph for S, this subgraph might not be connected. What I want to do is to include as few as possible extra nodes outside S, and make as most as possible nodes in S are connected pairwisely through a path. Is there any way to accomplish this?

    Thank you very much
  2. jcsd
  3. Apr 7, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    I'm not a graph theorist, but I think you should clarify what it means to accomplish your goal. Are you asking whether there is an algorithm to construct the required subgraph? - or are you asking whether there is a theoretical argrument that the required subgraph exists?
  4. Apr 8, 2012 #3
    I would like to know whether such subgraph exists or not. If it does exist, is there an algorithm to obtain this subgraph
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook