The tag has no wiki summary.

learn more… | top users | synonyms

-3
votes
0answers
26 views

Directed and undriected trees [on hold]

How many different directed trees can be obtained if we assign all possible orientation to the edges of an undirected tree having exactly 7 nodes? how many of them will be rooted(directed) trees?
5
votes
1answer
168 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 ...
1
vote
0answers
47 views

Can we make the weaker TPC tighter when we do the packing steiner trees?

The famous tree packing conjecture (TPC) posed by Gyarfas (see [1]) states: $\textbf{Conjecture 1}$. Any set of $n āˆ’ 1$ trees $T_n, T_{nāˆ’1}, . . . , T_2$ such that $T_i$ has $i$ vertices pack into ...
12
votes
4answers
889 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
267 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
116 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
51 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
185 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
180 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
166 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
266 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
283 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 ...