How to induce a minimal subgraph

  • Thread starter Thread starter cynthiaj
  • Start date Start date
AI Thread Summary
To induce a minimal subgraph from an undirected graph G with a subset S of nodes, the goal is to connect as many nodes in S as possible while adding the fewest additional nodes. The discussion raises the question of whether such a subgraph exists and if there is an algorithm to construct it. Clarification is sought on whether the inquiry pertains to the existence of the subgraph or the algorithmic approach to obtain it. The need for a theoretical argument or a practical algorithm is emphasized. Ultimately, the focus is on finding a method to achieve the desired connectivity among the nodes in S.
cynthiaj
Messages
2
Reaction score
0
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
 
Mathematics news on Phys.org
cynthiaj said:
Is there any way to accomplish this?

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?
 
Stephen Tashi said:
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?
I would like to know whether such subgraph exists or not. If it does exist, is there an algorithm to obtain this subgraph
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

I Find Smallest Subtree of G w/ Nodes from S
Replies
5
Views
2K
B Can you read my English on 4 colour theorem?
Replies
8
Views
2K
Strong Induction, Tangled Graph
Replies
3
Views
3K
A Cross section from subgraph in electron-proton DIS
Replies
3
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
Replies
1
Views
2K
Does This Graph Structure Form a Matroid?
Replies
1
Views
2K
Is Every Induced Subgraph with a Cut-Vertex a Block?
Replies
1
Views
2K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
I Optimization problem with multiple outputs: impossible?
Replies
6
Views
2K
Python Understanding Graph Neural Networks (GNNs) Tutorials & Examples
Replies
2
Views
2K

Hot Threads

Recent Insights

Back
Top