# Tagged Questions

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.

404 views

28 views

### Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
63 views

### Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
59 views

### If the inorder traversal of a binary tree produces ordered output, is the tree a binary search tree?

Given a binary search tree, it's easy to see that the inorder traversal returns values from the underlying set in order (according to the comparator that set up the binary search tree). My question ...
33 views

### Proof of a tree with a vertex of degree k and less than k vertices of degree 1

The question is : Does there exist a tree with a vertex of degree k and less than k vertices of degree 1? I tried a lot but it is impossible to find. There is no tree with a vertex degree k and less ...
70 views

### What does $\chi(Tree)\leq 2$ mean in graph theory?

I am reading an article about graphs in English. Does $\chi(Tree)\leq 2$ mean that each node has no more then $2$ children?
478 views

### Prim , Kruskal or Dijkstra

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . ...
69 views

### could a spanning tree graph be expressed by a lower triangular matrix?

Suppose a directed spanning tree graph $G$, there are $n$ nodes, and the root is node $1$. We express this graph by a matrix $M_{n\times n}$. If there is an directed edge from node $i$ to node $j$, ...
46 views

### About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
441 views

### How to calculate the expected maximum tree size in a pseudoforest

I would like to calculate the expected maximum tree size in a randomly generated pseudoforest of $N$ labelled nodes where self-loops are not permitted. Empty and single-node trees are also not ...
76 views

### Is this random binary tree finite?

Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) ...