For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

learn more… | top users | synonyms

0
votes
1answer
28 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
5
votes
1answer
110 views

Killer Tree! (one of my old questions)

There is a problem that killed me! but I couldn't solve it: We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.
0
votes
2answers
32 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
0
votes
1answer
39 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
3
votes
0answers
49 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
1
vote
0answers
40 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
0
votes
0answers
31 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
0
votes
0answers
20 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
2
votes
1answer
33 views

tree structure on classes of elements in GL_2 over a field with discrete valuation

this is my first question here, so I hope I am doing it right. :) I'm currently reading a paper about the tree of GL_2 over a discretely valued field (similarly to Serre). Here's the setting: $k$ an ...
14
votes
2answers
310 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
2
votes
1answer
57 views

Mathematics of genealogical trees

I really searched a lot but did not find anything meeting my needs: A place where questions of genealogy, especially the structural and combinatorial analysis of genealogical "trees" of descendants ...
3
votes
0answers
42 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
1
vote
1answer
25 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
0
votes
2answers
29 views

Determine the minimum number of weighings to find the counterfeit coin.

Here's the full problem: We have 20 coins, 1 of which is counterfeit (too light). Determine the minimum number of weighings to find the counterfeit coin. Okay so is used the formula $$h=\left ...
0
votes
1answer
26 views

Finding the number of spanning trees on a set of vertices.

I need to find the number of spanning trees on $V = \{1,2,3,4,5,6,7,8,9\}$, where $\{1,2,3,4\}$ are leaves. Can anyone tell me how?
1
vote
3answers
85 views

is MST a Steiner tree?

I am a little bit confused about MST and Steiner tree? Is an MST a steiner tree?? and suppose we are given a weighted undirected connected graph G = (V,E) and S ⊆ V is the smallest subtree of an MST ...
1
vote
2answers
55 views

When trees are the answer: what is the question?

For which optimization problems are (abstract) trees the best solution? E.g. binary search trees are somehow optimal data structures for quick search. But why for example do botanic trees grow as ...
2
votes
1answer
65 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
2
votes
1answer
173 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...
1
vote
2answers
180 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...
0
votes
1answer
72 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
1
vote
1answer
152 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
0
votes
0answers
25 views

A function for the branches of a tree

Imagine that we have to calculate the number of branches of a tree. Now I made a formula that associates the "level" (number of the times that a branch replicates itself) $k$ of the tree and the ...
0
votes
1answer
32 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
1
vote
2answers
43 views

Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server ...
0
votes
1answer
32 views

Distinct MST Edge Proof

Suppose that T1 and T2 are distinct MSTs for an undirected graph G. Let (u,v) be the lightest edge that is in T2 and not in T1. Let (x,y) be any edge that is in T1 and not in T2. What can you say ...
0
votes
1answer
21 views

Find MST based on new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
2
votes
2answers
70 views

Introductions to posets on algerbaic structures (Everything I need to know about them)

I need a good and complete introduction to Tree-like orders and partial orders on algebraic structures with one operations. I accept basic texts too. I'm looking for free online texts mostly because ...
2
votes
2answers
49 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
1
vote
1answer
20 views

How many spanning trees of a complete graph with an even number of vertices can be split in half by removing a single edge?

We have a complete Graph G with |V|=n . We know it has n^(n-2) possible spanning trees. How many of them could be split into two equal halves by removing a single edge?
0
votes
0answers
44 views

heavy path decomposition/heavy-light decomposition

I'm reading about the heavy path decomposition of trees and its application. I would like to know its time and space complexity. In addition, can the algorithm be implemented in distributed way? What ...
0
votes
0answers
19 views

Which cut-off for collapsing this tree?

I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of DNA regulatory motifs that are ~5-9 bp long sequences. An interactive ...
1
vote
1answer
69 views

Determine number of directed trees and rooted trees obtainable

I've been doing some exercices about graph theory and I find myself stuck on this one with no idea of to proceed. Here's the question : how many different directed trees can be obtained if we assign ...
1
vote
2answers
67 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
0
votes
1answer
48 views

calculate the proportion of n-node trees whose root has only one or two subtrees.

Could we use combinatorics and generating functions to calculate the proportion of n-node trees whose root has only one or two subtrees? Here is what I tried: The combinatorial construction for the ...
0
votes
0answers
29 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
0answers
14 views

What is a first-order dependency tree?

From the definition of Chow–Liu trees. Obviously, a tree is a graph with no loops; with first-order do they mean that it is a tree similar to those followed by a depth-first search?
3
votes
2answers
130 views

Number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves.

I've been trying to do the following exercise: The problem Find the number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves. I know that I should try to write an ...
0
votes
0answers
21 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
0
votes
1answer
37 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...
0
votes
1answer
112 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
2answers
56 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
1
vote
1answer
32 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
0
votes
1answer
50 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
1
vote
1answer
79 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
2answers
293 views

How many trees are in the spanning forest of a graph?

Spanning forest is defined by the following definition: A forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two ...
0
votes
0answers
41 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
0
votes
1answer
43 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
0
votes
1answer
54 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
1
vote
3answers
68 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...