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

385 questions
Filter by
Sorted by
Tagged with
1 vote
20 views

### Does influence graph have multiple directed edges?

so I am studying about graphs from the book discrete maths by Keneth Rosen 7th edition.Pg:645 However, I am bit unsatisifed with one of the statements from the book. So I would like to get it reviewed ...
21 views

### Tournament with directed edges [closed]

Prove that one can construct a finite tournament G with at least 101 vertices such that: for any subset S of 100 vertices of G, there is some vertex v for which all 100 vertices s ∈ S have a directed ...
23 views

### Firefighter problem - finding min-cut in capacitated network (Help)

As my final project my colleagues and I chose to research the firefighter problem. We could really use your help in the section of MIN-BUDGET regarding the DirlayNet (Directed layered network) ...
1 vote
37 views

### Odd girth of line digraph.

Are there any known results on the odd girth of the line digraph of a given digraph? By line digraph of a digraph $D$ having vertex set $V$ and arc set $A$, I mean the digraph whose vertex set is $A$ ...
1 vote
61 views

### Lower bound for the maximum number of vertices of a connected rooted sub-digraph of a simple acyclic digraph

Given a simple directed acyclic graph with $n$ vertices and $m$ edges, we get the maximum number of vertices over all connected rooted sub-digraphs of it. Connected rooted sub-digraph means here that ...
36 views

### Bounds on the spectral radius of a directed graph

Suppose $(G_n)$ is a sequence of simple directed graphs with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be a sequence of subgraphs obtained by ...
57 views

### How many arcs are required to guarantee the existence of cycles?

A directed graph is weakly connected if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph. We know that for an undirected ...
82 views

### Number of Branches on a Tree that spans a grid

I want to count the arrows of a tree that spans a $n$-dimensional grid in a certain way. Take a $n$-dimensional grid of equal side length $f$. I'll use $n=2$ and $f=4$ in this example, but the ...
26 views

### Are there any vertex-transitive digraphs with distinct in and out degree

It seems to me like a question that must have been answered somewhere before, but I haven't been able to find anything on this. Take a vertex-transitive digraph $\Gamma$, that is a directed graph, ...
56 views

### Producing even cycles in directed graphs - Alon and Spencer, Exercise 3.4

Show that there is a finite $n_0$ such that any directed graph on $n>n_0$ vertices in which each outdegree is at least $\log_2(n)-\frac{1}{10}\log_2\log_2n$ contains an even simple directed cycle. ...
1 vote
81 views

### Finding paths that satisfy criteria in a large weighted cyclic directed graph

I have a large cyclic weighted directed graph where weight is the duration in days of going from one node to another. The graph has about 1500 nodes and 100 thousand edges, and the average node in/out ...
1 vote
29 views

### Looking for resources on irregular expander graphs

I've been reading up on Expander graphs on the web, papers, books and surveys. However, all the resources I could find on Google is about regular, connected, non-bipartite (undirected) graphs. The ...
64 views

### How to calculate all cycles in a directed graph?

I am competing in the American Computer Science League (ACSL), and I get problems similar to the following. Look at this directed graph. Now tell me the number of cycles in said graph. These ...
83 views

### Prove that $\det(A A^T) = 0$ where $A$ is the incidence matrix of a directed graph

I would like to prove the following result about graphs: Given a node-incidence matrix $A$ of a directed graph, the determinant of $A A^T$ is $0$. The element $a_{ij}$ of the incidence matrix $A$ is ...
1 vote
32 views

### For every tree of shortest path there is a way of writing the adjacency lists such that there is a BFS thet returns this tree?

A directed graph G=(V,E) is given and I am asked to prove if there is a tree of shortest path of this graph that cannot be returned using BFS. Meaning to say if it is true or not that for every tree ...
1 vote
32 views

Let $G=(V,E,w)$ be a signed directed graph where every vertex $v\in V$ has out-degree $2$, and every directed edge $e\in E$ has sign $w(e)\in\{-1, +1\}$. A walk $z = (v_1, e_1, v_2, e_2, \ldots, v_{k-... 4 votes 1 answer 63 views ### Succinct represention of a condensed complete directed graph I'm working on research in multi-agent reinforcement learning, and in the experiments that I'm running now, my six agents are forming a social order. I've been analyzing these experiments for a while, ... 0 votes 0 answers 45 views ### Given a directed graph, can you determine if it can be drawn as a planar graph? Say a directed graph has loops and has nodes directed towards each other. I would like to know if there is an algorithm for determining if the graph can be drawn as a planar graph. 0 votes 1 answer 44 views ### Term to describe a subgraph of a digraph where no arcs go into it from outside What's the shortest way to describe a subgraph of a digraph where, in the original graph, no arcs go into it from outside? Is there a term for this? Note that it might or might not be connected. Here'... 0 votes 0 answers 34 views ### directed walk and a directed path Let D be a directed graph and let u and v be vertices (nodes). Prove that if D has a directed uv-walk then D also has a directed uv-path. I tried using the process that a walk P is the shortest uv-... 1 vote 1 answer 67 views ### Inequality on the number of paths in a graph Let$G$be an undirected graph with$n$nodes and let$a_k$denote the number of directed paths of length$k$. Prove that $$a_1 \leq \sqrt{n a_2}.$$ Note that$a \to b \to a$, where$a$and$b$are ... 1 vote 0 answers 76 views ### Directed Acyclic Graph Complexity Measures I have many (millions) of collider-less directed acyclic graphs (DAGs) (they're actually causal graphs, but that's unimportant for this question) I am using to model a process, and I would like to ... 0 votes 2 answers 64 views ### Is a 𝑢−𝑣 path followed by a 𝑣−𝑤 path is a 𝑢−𝑤 path. [closed] Can I say a 𝑢−𝑣 path followed by a 𝑣−𝑤 path is a 𝑢−𝑤 path. Because if there is a path from 𝑢−𝑣 followed by 𝑣−𝑤 I believe there should be a 𝑢−𝑤 path. I don't know how to prove it. EDIT: A 𝑢... 3 votes 1 answer 562 views ### Can a DAG have strongly connected components? It seems to me, a DAG (the directed graph has no cyclic.) is not possible to have strongly connected components (SCC), but it can have weakly connected components (WCC). The definition of SCC and WCC: ... 0 votes 0 answers 62 views ### Existence of source/sink in directed acyclic graph with connected complement The statement I would like to prove is the following: For any connected acyclic digraph$G=(V,E)$there exists a source or sink vertex$v\in V$such that the graph complementary to that vertex, ... 0 votes 0 answers 35 views ### Finding MDST in subgraph is enough for MDST problem in the original graph Let$G = (V, E, w)$be strongly connected graph. Show that there exists a subgraph$G′ = (V, E′, w)$of$G$with$|E′| \le 2(n − 2)$such for every$r\in V$, an MDST of$G′$rooted at$r$is also an ... 2 votes 2 answers 113 views ### Computing Longest Simple Path in a Particular Digraph Let$D$be a digraph as follows: I want to compute a longest simple path of it. For an acyclic digraph, there is a method I can run in Python that returns a longest path, but$D$is not acyclic. I ... 2 votes 1 answer 57 views ### Number of directed graphs on a$3\times 3$grid where every vertex has both indegree and outdegree$\ge 1$Consider nine vertices arranged in a square$3\times 3$grid. Compute the number of directed graphs that can be drawn on the grid by connecting every vertex to its immediate horizontal and vertical ... 0 votes 0 answers 22 views ### Graphs - Probability of reaching destination in a graph. So I am given a graph with a bunch of nodes and links, where links "activate" with a certain probability and can also fail with non-zero probability. We have a source node and a destination ... 3 votes 1 answer 113 views ### How is the expression for Kirchoff's Law obtained from this incidence matrix? I am following along Chapter 8 ("Applications"), Section 8.2 ("Graphs and Networks") from Gilbert Strang's Introduction to Linear Algebra (4th edition). In this section he shows ... 0 votes 0 answers 29 views ### Property of the incidence matrix of a directed graph I would like to prove the following result about graphs: Consider a finite set V with an antisymmetric and transitive relation, but strictly non-reflexive, i.e. no element is related to itself (it is ... 0 votes 1 answer 52 views ### Discrete Mathematics - Trees and Relations Question I am completely stuck on this multiple choice trees question. In this multiple-choice question, more than one option can be correct. I believe this is a trees question; if it is not, then I have gone ... 2 votes 1 answer 40 views ### Find cycles with fixed number of edges without shared vertices in a directed graph I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ... 0 votes 0 answers 12 views ### Are there recent review papers on random digraph models? I am developing interest in random digraphs. I would like to have a quick survey of the history, concepts and latest developments in random digraph models. Is there some comprehensive contemporary ... 2 votes 1 answer 107 views ### What is the expected length of the longest path in a DAG? Let's consider a random directed acyclic graph (DAG) with$n$vertices and$m$edges. What is the expected length of the longest path in this graph? Is there a function$f(n,m)$that can approximate ... 1 vote 0 answers 45 views ### Question about minimum of the stationary distribution of a random walk on a directed graph Suppose there is a random walk process on a simple strongly connected directed graph$G=(V, E)$. The random walk follows a transmission matrix in the form$M=AD^{-1}$, where A is the adjacency matrix ... -2 votes 1 answer 39 views ### how to formulate the following properties formally? Let (N, E, l), be a labeled directed graph, where N is a set of vertices, E ⊆ N×N is a set of edges, and l: E → L is a function assigning labels from a set L to edges. Let source and target be ... 2 votes 2 answers 183 views ### Finding contracted vertices in a weighted directed graph Consider an edgeless graph $$g:=(V,E):=(\{1,2,\ldots,n\},\emptyset)$$ and an embedding of$g$on the 2-dimensional Euclidean plane$\omega:V \rightarrow \mathbb{R}^2$. Consider the surjection $$\phi:V ... 0 votes 0 answers 139 views ### Global efficiency for weighted directed graphs? I would like to compute the global efficiency of a weighted directed graph. When looking the appendix of Rubinov & Sporns (2009) it seems like there's no difference in the computation:$$ E^\text{... 0 votes 0 answers 159 views ### Can Dijkstras Algorithm be used for directed graphs with negative edges in only the initial node? Imagine a directed graph in which the only negative edges are those that leave the initial node s; but all other edges are positive. Can Dijkstra’s algorithm, started at s, fail on such a graph? Prove ... 1 vote 0 answers 25 views ### Number of sink vertices connected to a vertex in a directed acyclic graph I'm looking for a term in graph theory for the number of sink vertices (or end vertices) connected via a directed path to each vertex in a directed acyclic graph. I mocked up a sample network here, ... 1 vote 1 answer 128 views ### Directed graph branching Let$G = (V, E)$a directed graph then a$\textit{branching} B \ \subseteq E $is a subset of edges such that there is at most one incoming edge for each vertex$v \in V$. Let$I = \{B \mid \text{ $... 0 votes 0 answers 31 views ### Shortest paths: Does$d(s, t) = d(s, v) + d(v, t ) $always hold if$v \in p $where p is the shortest path between$s, t\$?

Now I know that there is a distinction between single source shortest path algorithms and all-pair shortest path algorithm . My question is the following: If we solve the single source (let's say s ) ...
108 views

### What type of Mathematics, if any, is this? (On curiosities associated with a logo.)

I'm not sure whether I have articulated my curiosity well enough here. Please, therefore, bear with me if I need to edit the question, and please forgive me if this is otherwise a nonsense question ...
50 views

### Graph theory: name for a strongly connected component where every edge is bidirectional?

Hi :) I was wondering if there is a term for a strongly connected component in a directed graph where every edge in the component is bidirectional. E.g. Graph1 would qualify, but graph2 would not, ...
78 views

### What "tool" to extrapolate traffic data on graph used for routing (Open Street Maps).

Background (non-math): I'm planning to use Open Street Maps data to find the fastest route by car between points. Data is a directed graph where vertices represent locations, and edges are routes. ...
480 views

### Why can matrix rounding be seen as a max flow problem?

For a general max flow problem, we know that each intermediatte node must give away the same amount of flow it receives. Besides this, we also know that the amount of flow that leaves the origin node (...
27 views

### Is it possible to have more than one complete directed graphs? And if yes, how many? I found a formula but I can't make sense of it.

3Cn2 = 3[num of arcs in undirected graph for some reason] Is the formula I found relating to this, I would imagine it means for every node you can either have an arc pointing to it, from it, or both ...