Timeline for on counting of special case of trees on a graph
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 4, 2010 at 13:05 | comment | added | katsarola | Of course, you are right. | |
| Sep 3, 2010 at 19:47 | comment | added | JBL | No, a path with four vertices is not an induced subgraph of a cycle on four vertices. | |
| Sep 3, 2010 at 19:20 | comment | added | katsarola | @David Speyer : Lets G be the cycle graph abcda and H the graph abcd. Then H is induced by G and is a tree but not an edge-tree. Forgive me if I miss something obvious, but did you mean "..S be a proper subset of vertices of G"? | |
| Sep 3, 2010 at 18:05 | vote | accept | katsarola | ||
| Sep 3, 2010 at 16:36 | comment | added | David E Speyer | The point of this comment is to explain why your definition is the same as "induced trees". Let S be a set of vertices of G. Let H by the subgraph induced by S en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs. I claim that there is an edge-tree with vertex set S if and only if H is a tree. Proof: Clearly, if H is a tree, it is an edge tree. Now, let T be a tree with vertex set S. Suppose that (u,v) is an edge of H not in T. Trees are connected, so there is a path through T from u to v. Adding the edge (u,v) to this path shows that T is not an edge-tree. | |
| Sep 3, 2010 at 16:27 | answer | added | Tony Huynh | timeline score: 3 | |
| Sep 3, 2010 at 15:57 | comment | added | David Eppstein | So an edge-tree is what is more commonly called an induced tree, right? | |
| Sep 3, 2010 at 15:40 | comment | added | katsarola | @Gjergji Zaimi : I am looking for a theorem which will help me to efficiently enumerate edge-trees of a graph. So if there already exists such an algorithm, I would love to know. | |
| Sep 3, 2010 at 15:08 | comment | added | Gjergji Zaimi | Among other things this theorem you are looking for will give the number of subtrees of a tree. This suggests there is no closed form of the number of edge-trees for most graphs. Or are you looking for an algorithm? | |
| Sep 3, 2010 at 15:06 | comment | added | katsarola | @Tony Huynh: that is correct. Lets assume that we want to count the number of maximal edge-trees (edge-trees that no edge/vertex can be added without forming an edge-cycle) or edge-trees of size k. | |
| Sep 3, 2010 at 14:51 | comment | added | Tony Huynh | Well, technically katsarola wanted to count edge-trees, not necessarily spanning edge trees, even though the Matrix-Tree theorem counts spanning trees. If spanning edge-trees are wanted, then there is 1 if the graph is a tree, and none otherwise. If it's edge-trees that are wanted, it looks like we just want to count induced subgraphs that are trees. | |
| Sep 3, 2010 at 14:47 | answer | added | Nekura | timeline score: 1 | |
| Sep 3, 2010 at 14:44 | comment | added | Louigi Addario-Berry | By your definition, if $u$ and $v$ are joined by an edge in $G$, then the path $u,v$ is an edge cycle. So any spanning tree of a graph with at least two vertices has an edge-cycle. Maybe you want to change your definition of edge-cycle to require that the path contain at least three vertices? | |
| Sep 3, 2010 at 14:38 | history | edited | katsarola | CC BY-SA 2.5 |
improved formatting
|
| Sep 3, 2010 at 14:11 | comment | added | katsarola | If by ambient graph, you mean the graph G, my answer is yes. | |
| Sep 3, 2010 at 14:10 | history | edited | katsarola | CC BY-SA 2.5 |
improved formatting
|
| Sep 3, 2010 at 13:55 | comment | added | darij grinberg | Or does "adjacent" mean "adjacent in the ambient graph"? | |
| Sep 3, 2010 at 13:55 | comment | added | darij grinberg | What is the difference between "no edge-cycle" and "no cycle"? | |
| Sep 3, 2010 at 13:38 | history | asked | katsarola | CC BY-SA 2.5 |