The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
194 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
4answers
905 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 ...
5
votes
1answer
275 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
0answers
123 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 ...
2
votes
0answers
53 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
0answers
206 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
3answers
202 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
1answer
172 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
1answer
279 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
1answer
324 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 ...