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

10
votes
0answers
135 views

Free medial magmas

A medial magma is a set $M$ with a binary relation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor $\mathsf{Set} ...
6
votes
0answers
320 views

Certain permutations of the set of all Pythagorean triples

The fact that the set of all primitive Pythagorean triples naturally has the structure of a ternary rooted tree may have first been published in 1970: http://www.jstor.org/stable/3613860 I learned ...
4
votes
0answers
23 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: ...
4
votes
0answers
322 views

Algorithm for generating homeomorphically irreducible trees of size n

In this video they talk about generating all the homeomorphically irreducible trees of size 10. I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
4
votes
0answers
99 views

Identify this combinatorial construction

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked ...
4
votes
0answers
123 views

Are almost all rooted trees asymmetric?

It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric. By which argument do I see whether almost all rooted trees are ...
3
votes
0answers
53 views

Condition for a graph to have only one MST (Minimum Spanning Tree)?

Can somebody tell me if there is a condition for an edge-weighted graph to have exactly one MST? I know that it can have more minimum spanning trees, but can it have only one? Thanks in advance!
3
votes
0answers
109 views

Associativity of the tensor product of dendroidal sets

For any smal category $A$, I shall write $\widehat A$ for the category $[A^{\text op}, \mathbf{Set}]$ of presheaves on $A$, and $y_A\colon A \to \widehat A$ for the Yoneda embedding relative to $A$. ...
3
votes
0answers
96 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
3
votes
0answers
53 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
3
votes
0answers
63 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 ...
3
votes
0answers
51 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 ...
3
votes
0answers
134 views

Mathematical notation for formulas involving trees

I am working on document that requires me to write such things as "$T_1$ is a descendant of $T_0$", or "$N_1$ is an parent of $N_2$". For now, I've been highjacking set notation for use in formulas, ...
3
votes
0answers
191 views

Number of spanning arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
2
votes
0answers
31 views

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
2
votes
0answers
30 views

Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
2
votes
0answers
84 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
0answers
71 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
0answers
57 views

Counting unlabeled and non-uniquely labeled trees

I recently learned about Cayley's formula, which states that the number of trees on $n$ labeled vertices is $n^{n-2}$. As I understand it, this works because we can prove that there are $n^{n-2}$ ...
2
votes
0answers
71 views

Examples of forcings which add no “definable” Aronjain tree

Maybe a bit board question but: Fixing a regular cardinal $\kappa$ in the ground model, I am looking for examples of set forcing notions which preserve regularity of $\kappa$ and add no new $\kappa$ ...
2
votes
0answers
44 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
2
votes
0answers
40 views

How can I infer order from partially ordered discrete sequences?

A really interesting problem that I can't stop thinking about! Have run in to this a couple of times but yet to find a smart approach to either solve or frame this problem. This is my try at ...
2
votes
0answers
99 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
2
votes
0answers
41 views

What are the automorphisms of an $n$-regular tree?

Let $T$ be the connected tree in which each vertex has $n$ neighbors. (So $T$ is infinite.) What is the full automorphism group of $T$?
2
votes
0answers
94 views

Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union ...
2
votes
0answers
74 views

Groups acting on (regular) trees with finite quotient

Let $T$ be a regular tree, and suppose that $G \leq \mathrm{Aut}(T)$ has finite quotient graph, $T / G$. Is it true (in general) that $G$ will have trivial centralizer in the full automorphism group? ...
2
votes
0answers
854 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
2
votes
0answers
112 views

A few questions about a relationship between some integer sequences and infinite recursive trees

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences: Hofstadter G-sequence: $a(n)=n-a(a(n-1))$ Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$ He says ...
2
votes
0answers
96 views

How matroids can help me locating trees inside a graph?

Background I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids? What I am looking for ...
2
votes
0answers
82 views

Embedding tree metric isometrically into $\ell_\infty$

I just started (independent) learning on metric embeddings from the Fall 2003 offering of the course at CMU. I have a limited mathematical background and alas, it made me stumble at the first exercise ...
1
vote
0answers
43 views

How to mathematically judge if there is a spanning tree in a graph?

Given a graph $G=(V,E,A)$ where $V$ is the set of the vertices, and $E$ is the set of sides, and $A$ is the adjacency matrix of dimension $n\times n$. $G$ is undirected or directed. We define the ...
1
vote
0answers
19 views

All possible depth first spanning trees of a directed graph.

I am looking for an algorithm that generates all possible depth first spanning trees of a directed graph that has a known root.
1
vote
0answers
25 views

Is there a polynomial time algorithm for Poly-trees (oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0answers
39 views

Existence of increasing pair of labeled trees in an infinite sequence

Assume labeled rooted trees with labels from a fixed set $\{1\ldots m\}$. For a tree $T$, we have: $V(T)$ the set of vertexes, $root(T)$ the root of the tree, $l_T: V(T)\rightarrow \{1\ldots m\}$ ...
1
vote
0answers
58 views

The number of edges in a tree is $n-1$

I am trying to prove that the number of edges in a tree is $n-1$ where $n$ is the number of vertices. I do not wish to use induction. I already have established that a tree is a planar graph. Now my ...
1
vote
0answers
35 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
1
vote
0answers
39 views

Traversing multi-way tree, computational complexity

This is a computational challenge. I am looking for a clever simplification or heuristic. Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do ...
1
vote
0answers
26 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
0answers
91 views

How to find the number of connected components of a graph by using its 16x16 adjacency matrix?

Good day, I have this exercice that provides me with the 16x16 matrix of adjacency of a graph and it asks me to find the number of connected components of the graph and I need to give a spanning tree ...
1
vote
0answers
40 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 ...
1
vote
0answers
46 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
1
vote
0answers
27 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
0answers
30 views

Help with proof about merge two heaps to one heap…

We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements). We know that the smallest element at $H_1$ is bigger the root (the biggest element) ...
1
vote
0answers
40 views

Probability and search Tree

I need some help with the following question. Given the random permutations of $ n > 2 $ numbers. Now, creating a binary search tree and puting it the organs one by one. Denote the input organs ...
1
vote
0answers
28 views

How many pure trees with a fixed number of nodes exist?

How many pure trees of size (number of nodes) $n$ exist? Apart from having this fixed size, the trees can be arbitrary. The sequence starts like this: Here's the beginning of the sequence:
1
vote
0answers
13 views

Graph invariants for rooted trees

I'm looking for a few graph invariants (that have been studied before) that help distinguish rooted trees. I have a large, real-world collection of these graphs and I'd like to see what has been ...
1
vote
0answers
44 views

Euclidean Minimum Spanning Tree Property

Is the following statement about Euclidean MSTs true, and if so could someone help me with a proof? Between any two nodes, the EMST minimizes the maximum edge cost of any edge required to traverse ...
1
vote
0answers
63 views

Multiway tree to Binary Tree

A multiway tree T can be represented as a binary tree T~ by using the firstChild and nextSibling pointers. If we think of the firstChild link as being the left link and the nextSibling link as being ...
1
vote
0answers
55 views

Ordinals as Trees

I'm trying to understand countable ordinals and their tree representation. I understand that $\omega$ is the first "non branching tree" of infinite height. I also understand that the exponent of ...
1
vote
0answers
30 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...