The spanning-tree tag has no wiki summary.

**3**

votes

**0**answers

111 views

### Characterizing graphs with $k$ edge-disjoint minimum diameter spanning trees

Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to $k$ edge-disjoint spanning trees by Frank and Szegõ [3]. ...

**2**

votes

**1**answer

127 views

### Maximum number of hyperedges on a hypergraph without a spanning tree

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges ...

**11**

votes

**0**answers

112 views

### On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects:
spanning trees of a grid graph, with no corridor
where a corridor is a vertex having exactly two neighbors, on ...

**5**

votes

**1**answer

257 views

### Minimum Spanning Tree of Graph with Unknown Weights

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we ...

**12**

votes

**4**answers

916 views

### Graphs in which every spanning tree is an independency tree

It follows from this question
and the corresponding answers, that the complete graphs and the cycles are precisely the graphs
$G$ having the property that, for every spanning tree $T$ of $G$, the ...

**6**

votes

**1**answer

290 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**3**

votes

**0**answers

138 views

### Matrix-tree for matrices with constant diagonal

I've got a symmetric matrix $A$ whose entries are in $\{0,-1,1\}$, with the diagonal entries all equal to $1$. I'm interested in finding a combinatorial description of the entries of the inverse of ...

**3**

votes

**1**answer

86 views

### rainbow spanning tree

In graph G, every edge has a color. Rainbow spanning tree is a spanning tree where all edges have different colors.
I want a polynomial algorithm to find such tree if exists any
Anyone can help?

**2**

votes

**0**answers

282 views

### Incremental minimum spanning tree

Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq ...

**0**

votes

**3**answers

260 views

### Minimize diameter of a tree

Hi! I have an acyclic undirected unweighted connected graph (a tree :) ), and I have to disconnect an edge and create a new one to minimize the diameter.
For now, I do a bfs on a arbitrary node, find ...

**4**

votes

**1**answer

176 views

### Divisibility Relation for Spanning Trees of a Graph

Let $A = \big[{1\ 1\atop 1\ 0}\big]$, and let $G_n$ be the graph whose adjacency matrix is
$A^{\otimes n}$. Also let $\kappa(G)$ denote the number of spanning trees of $G$. From a significant amount ...

**1**

vote

**1**answer

360 views

### Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...

**3**

votes

**1**answer

423 views

### How random are random spanning trees?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ...

**1**

vote

**1**answer

2k views

### 3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree

I read that the Euclidean Minimum Spanning Tree (EMST) of a set of points is a subgraph of any Delaunay triangulation. Apparently the easiest/fastest way to obtain the EMST is to find the Deluanay ...