# Questions tagged [directed-graphs]

For questions about directed graphs. In a directed graph, each edge is an ordered pair of vertices; we think of it as pointing from one to the other. Use with the (graph-theory) tag.

414 questions
Filter by
Sorted by
Tagged with
39 views

### Lower bound on the number of transitive sub-tournaments of size k in a tournament of size N.

Given a tournament of size $N$, what are the lower bounds on the number of transitive sub-tournaments of size $k$? What about specific values of $k$? For $k = 3$ I know the number of transitive sub-...
• 23
1 vote
34 views

### Worst Case Solution for directed Chinese Postman Problem

The Problem Let $G$ be a directed graph with $n$ vertices. How long is a shortest circuit that visits every edge in the worst case? That is how long is the solution to the directed Chinese Postman ...
• 11
34 views

### Is it possible to construct a regular directed graph with 9 vertices, 36 directed edges, and no cycles of length 3 or lower? [closed]

(I'm somewhat new to graph theory so I apologize if I get some terminology wrong) Is it possible to make a directed graph satisfying the following properties?: The graph has 9 vertices. The graph is ...
• 17
39 views

### Find unique solution to noninvertible system of linear equations, subject to constraints

I have the following problem: I have a directed graph with $M$ nodes and $K$ edges. Each edge $E_j$ has a weight $w_{1,j} + w_{0, j}$ at the end of the edge and $w_{0, j}$ at the start of the edge. ...
• 103
16 views

• 2,150
23 views

### Equivalence of DAGs after conditioning on the identity of two variables

Let $(G,p)$ be a Bayesian network* with a leaf (child-less node) $X$, such that there is a root (parent-less node) $Y$ in $G$ which has the same range as $X$. Moreover, suppose that we can "...
• 119
37 views

### Shortest super-path to complete multiple paths to vertices.

I have a graph with multiple vertices. Let's say all vertices are connected to each other, and all edges are equal weight. I have multiple directed paths I have to take across this graph, but I want ...
• 101
1 vote
40 views

### DAGs, d-separation, paths of two vertices: confusion

I'm taking a class on Bayesian probability. Briefly, my question is about directed acyclical graphs (DAGs) and d-separation of parent and child vertices, conditional on the parent. (This question ...
• 21
1 vote
29 views

### Is there a linear bound on the sum over branch vertices of minimum distances to leaves multiplied by outdegree?

Let's consider a directed rooted tree $T$ and define a function $f\colon V(T) \to \mathbb N$ equal for each vertex $v$ to the distance to the nearest leaf (in the subtree with root $v$). Formally f(...
• 7,016