# 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.

347 questions
Filter by
Sorted by
Tagged with
15 views

### Terminology for rooted directed graph with no directed cycles

I'm working on a algorithm that creates a rooted directed graph where cycles exist, but no directed cycles. So the set of vertices in this graph contain a root and leaves (just like a tree), it allows ...
• 33
6 views

### Is there any special condition on finding the inital spanning tree for a minimum cost flow problem?

I was wondering... When we are working with a standard minimun cost flow problem, is there any additional condition on the initial basis besides defining a spanning tree? Take the graph below as an ...
• 609
9 views

### Clustering of directed graphs satisfying priority constraints

I recently ran into a problem related to directed graph clustering, but don't know how to solve it. There is a directed acyclic graph $G = (V,E)$, where $V$ is the set of vertices, and $E$ is the set ...
• 431
1 vote
27 views

### Number of loops in a type of directed multigraph

I am interested in finite directed multi-graphs with one connected component, where each vertex comes with exactly 1 edge pointing out from it, which can point to another vertex, or itself. So self-...
• 308
24 views

### Dynamic programming efficient network

Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting vertex u to ending vertex v, with the constrain that the vertices and edges will have an ...
80 views

### Find the shortest path in a graph which must pass certain nodes.

I have a directed weighted graph with 16 vertices. One node (bottom left side) is labeled "S" as the starting point, the objective is to find the shortest ...
15 views

### Find edges that if removed increase value of shortest path in weighted directed graph

Let's say I have a directed weighted graph $G=(V,E)$ where the weights are all positive. Let $d_G(s,t)$ be the value of the shortest path in $G$ between two nodes $s$ and $t$. I want to find the set ...
35 views

### Perron-Frobenius theorem for reducible non-negative matrices

Let $M$ be a non-negative matrix ($M_{ij}\geq 0$ for all $i,j$). If $M$ is irreducible, then we know that there exists an eigenvalue $\lambda$ of $M$ that equals the spectral radius $\rho(M)$ and has ...
• 1,083
16 views

### Fiedler Vector for directed and not strongly connected graph

Anyone know if there is any work that deal with Fiedler vector graph partition, for the case of connected, directed, but not strongly connected graph? Thanks
• 1
1 vote
23 views

### Deduce the undirected edge version of Menger's theorem from the directed version

Menger's theorem says, in directed graph $G$, $k$ is the maximum number of arc-disjoint $st$-dipaths if and only if the size of the minimum $st$-cut is $k$. Use this version of Menger's theorem to ...
• 13
17 views

### Find the upper bound probability of a collision in a packet scheduling problem - Exercise

Let $G$ be a graph representing a network. On this network we have $N$ packets, each with a starting node, a path and an end node. Time is discrete, so each packet move only at a certain instant. When ...
19 views

### Calculating number of edges in a directed graph with a small constraint.

I have a graph of events. Every time '$t$' only $2$ events may occur (i.e. $2$ vertices). Each vertex is unique and let's define it as: $V(event, t)$ where: event is either "$1$" or "$2$...
31 views

### Cliques in an arbitrary undirected graph

I have to describe (no pseudocode needed) how to find large cliques in an arbitrary undirected graph. All vertices have to be connected with each other and crossing is allowed. This is one approach: ...
48 views

### Ordered Graph Problem

Let G = (V, E) be a directed graph with nodes v1, v2, . . . , vn. We say that G is an ordered graph if it has the following properties. (i) Each edge g Let G = (V, E) be a directed graph with nodes v1,...
19 views

### Given a directed graph with $n$ nodes where min out degree of a node is $m$ and max in degree is $1$, prove $n>2m$

Directed graph with $n$ nodes with the following constraints: Maximum in degree of any node: 1 Minimum out degree of any node: $m$ Prove that $n>2m$ I tried proof by contradiction, saying that let ...
28 views

### Each directed graph Has 0 crossing edges in Some DFS Run?

I found the following claim online: For each directed graph, There is DFS run such that it contains 0 crossing edges. Why is this correct at all? I think I found a counter example, consider a graph ...
• 1
31 views

### Relationship between the minimum cost rooted k-edge connected subgraph and the unrootd version in undirected graphs

In the undirected rooted k-edge connected subgraph problem, the goal is to find a minimum cost subgraph in which there are k edge-disjoint paths between the root and each vertex in the graph. The ...
• 137
1 vote
20 views

### Islands and bridges proove that after removing a bridge there are at most 3 bridges which let you get to any other island

The city is built on islands, some of which are connected by bridges. There is a maximum of one bridge between two islands, you can only go one way over the bridge, but you can get from any island to ...
• 161
62 views

### Möbius inversion for categories instead of directed graphs

In Tom Leinster, The Euler Characteristic Of A Category, the author generalizes the notion of Möbius Inversion for posets to finite categories. This violates the principle of equivalence. A possible ...
44 views

### Ordering vertices of a bipartite digraph satisfying a specific property

Let $D$ the bipartite digraph with vertices bipartitions $A$ and $B$ such that it has only arcs of $A$ to $B$. It easy to see that $D$ is acyclic (not contains directed cycle). I know that $D$ has a ...
• 81
7 views

### How can one efficiently group the nodes of a directed acyclic graph to make collective nodes?

The adjacency matrix $A$ of the transitive closure of a directed acyclic graph can have a checkerboard' pattern like A = \begin{pmatrix} 0 & ? & ? & ? & {\bf a} &...
94 views

### convert any non DAG into DAG (Directed acyclic graphs)

It is always possible to convert any non DAG into a DAG, by changing its order, if not limiting the number of changes. Is this true? Is there a proof? [Newly Updated/Edited for exact definitions] Non ...
• 167
1 vote
53 views

### For which directed graphs does Pascal's recursive method work for finding the number of paths?

In math contests, such as those run by the University of Waterloo CEMC in Canada or the AMC series of contests in the US, there are frequently questions of the following kind: Given an $m\times n$ ...
• 3,213
72 views

While playing `rock paper scissors'' with my daughter it became obvious that she wanted to add a few elements to the game, Specifically the fox and the well. A bit later we added the match and the ...
• 429
1 vote
98 views

### Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)

Let's say we have $n$ points numbered from $1$ to $n$. What is the maximum number of directed edges possible on a graph with these $n$ points: without any cycle of length $\leq k$, for example ...
• 1,597
162 views

### Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph. I am aware that this question may be considered a duplicate of this one: The ...
92 views

• 5,384
146 views

### Does there exist a tournament with exactly two Hamiltonian paths?

A tournament is a complete directed graph. A Hamiltonian path is a path that crosses each vertex exactly once. My conjecture is no. I have tried using induction, proof by contradiction, all to no ...
• 496
1 vote
76 views

### Directed graph isomorphism condition correctness

I'm currently working on a project and I've hit a bit of a stumbling point regarding one part related to directed graph isomorphism. To put it short, I have to find all graphs with N = 1,2,3,4 ...
• 13
30 views

96 views

### Distance between vertices in a directed graph

We know that an unweighted undirected graph $G = (V(G), E(G))$ with the geodesic distance $d_{G}$ is a metric space (if we allow $d_{G}$ to attain $\infty$ or if $G$ is connected)(we'd better say an ...
• 246
1 vote
95 views

### Canonically enumerating all finite transversals of this curious labeled directed graph

In a paper I am working on, a puzzling "game" has arisen. In this problem, I am trying to canonically enumerate all ways of traversing a specific labelled directed graph. However, this is ...
• 3,766
72 views

### Show that the set of nonnegative numbers partially ordered by divisibility has a unique maximal element.

I came across the following question while studying partial orders: Consider the nonnegative numbers partially ordered by divisibility. Show that this partial order has a unique maximal element. ...
• 45
The book from which I am studying graph theory has this definition of a covering edge: If $a$ and $b$ are distinct nodes of a digraph, then $a$ is said to cover $b$ if there is an edge from $a$ to $b$...