Timeline for Difference between a sub graph and induced sub graph.
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21, 2019 at 16:48 | answer | added | Divesh Kumar | timeline score: 2 | |
| Dec 19, 2017 at 1:58 | answer | added | user3492040 | timeline score: 5 | |
| Feb 14, 2015 at 9:52 | answer | added | M. Javaid | timeline score: 2 | |
| Nov 9, 2014 at 12:07 | vote | accept | patang | ||
| Nov 9, 2014 at 12:03 | answer | added | Peter | timeline score: 58 | |
| Nov 9, 2014 at 12:00 | comment | added | Peter | Maybe, I am wrong with the expression subgraph in case of minors. But what is true, that a general subgraph can have less edges between the given vertex-set than the original graph. | |
| Nov 9, 2014 at 11:53 | comment | added | patang | @Peter I'm pretty confused by this name 'induced' ,what induction does this subgraph does... | |
| Nov 9, 2014 at 11:49 | comment | added | Peter | Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph. | |
| Nov 9, 2014 at 11:47 | comment | added | patang | @Peter I don't get in which case can we merge vertices: in induced subgraph or subgraph | |
| Nov 9, 2014 at 11:46 | comment | added | Peter | Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced. | |
| Nov 9, 2014 at 11:40 | comment | added | patang | @Peter can you just elaborate your example as I don't know what a minor is ? | |
| Nov 9, 2014 at 11:37 | comment | added | Peter | An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced. | |
| Nov 9, 2014 at 11:31 | comment | added | Tuomo Lempiäinen | Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph? | |
| Nov 9, 2014 at 11:22 | history | edited | patang | CC BY-SA 3.0 |
edited title
|
| Nov 9, 2014 at 11:14 | history | asked | patang | CC BY-SA 3.0 |