Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
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-...
Will's user avatar
  • 23
1 vote
1 answer
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 ...
Felix's user avatar
  • 11
0 votes
1 answer
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 ...
Zortexxx's user avatar
0 votes
1 answer
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. ...
Alex V.'s user avatar
  • 103
0 votes
0 answers
16 views

Neighbouring cover in a directed graph

I am not sure if this type of problem has been studied before, so it would be great to receive some guidance. Consider a directed graph G=(V,E). We define an in-neighbourhood cover as a subset $W\...
Andres Fielbaum's user avatar
2 votes
0 answers
50 views

Converting "improper" partial order to total order

I suspect that if I knew what to search for, this would be easy to find an answer to, but I don't know what the proper name is for the input portion of the problem statement. I have a set and a ...
BCS's user avatar
  • 663
0 votes
0 answers
37 views

Lengths of paths between vertices in a directed graph

Let $G$ be a finite directed graph and $v,u$ be two vertices of $G$. I am interested in the following question: For which $n\in\mathbb{N}$ there exists a path of length $n$ from $v$ to $u$? I know ...
QMath's user avatar
  • 427
2 votes
1 answer
52 views

Graph isomorphism checking/detection for directed acyclic graphs

The graph isomorphism problem is hard for an arbitrary graph, and certain classes of graphs have been proven to be "GI-complete", which as I understand means they can be reformulated in ...
John Cataldo's user avatar
  • 2,649
1 vote
2 answers
82 views

Flowcharts or processes as mathematical objects.

I have been looking for a couple of months for a way to formally define flowcharts as mathematical entities, but have not found much. Since they usually look like graphs, I would expect a definition ...
Bryan Castro's user avatar
-1 votes
1 answer
45 views

What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]

Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
Bark Jr. Jr.'s user avatar
1 vote
0 answers
28 views

Prove one specific Upper bound of the minimum time of a p-processor schedule

In spring18 mcs.pdf, it has Problem 10.26: We want to schedule n tasks with prerequisite constraints among the tasks defined by a DAG. (a) Explain why any schedule that requires only p processors ...
An5Drama's user avatar
  • 416
0 votes
1 answer
48 views

In the digraph, the shortest positive length closed walk through a vertex is a cycle through that vertex.

In spring18 mcs.pdf, it has Problem 10.4: Problem 10.4. (a) Give an example of a digraph that has a closed walk including two vertices but has no cycle including those vertices. (b) Prove Lemma 10.2....
An5Drama's user avatar
  • 416
1 vote
5 answers
71 views

I’m trying to find all of the cycles of a directed graph. Is there a more efficient way to do this?

Here’s the graph: My current strategy is to make an adjacency matrix, then follow it, like if A can go to B, then I go to B’s row and see which points B can go to, all the way until I reach the ...
Ian Lee's user avatar
  • 11
0 votes
0 answers
20 views

Mixed integer linear programming - connection of a directed graph

I am doing a simple optimization model of a directed graph with one source node and a couple of load nodes. Every load node connected to a source node, sometimes directly and otherwise over another ...
maki_b7's user avatar
0 votes
2 answers
123 views

Betweenness problem algorithm counter-example round 2

I asked in previous question about algorithm proof or counter-example. Alex kindly provided a counter-example, I took my time studying it and why it failed producing a valid ordering, so I came with ...
user avatar
2 votes
1 answer
182 views

Betweenness problem algorithm counter-example

Betweenness is an algorithmic problem in order theory about ordering a collection of items subject to constraints that some items must be placed between others. It has applications in bioinformatics ...
user avatar
1 vote
1 answer
58 views

Does a strongly connected component necessarily have a Hamiltonian path or cycle?

In a general directed graph, does a strongly connected component necessarily have a Hamiltonian path or cycle? I don't think so, and I've tried to come up with compact counter example, but have yet to ...
sadcat_1's user avatar
  • 259
1 vote
1 answer
17 views

In a directed series-parallel graph, is every pair of non-terminal nodes connected by at most one path?

The title pretty much says it all. A directed graph $G = (V, E)$ is two-terminal series-parallel, with terminals $s_G$ and $t_G$, if it can be produced by a sequence of the following operations: ...
graphtheory123's user avatar
2 votes
0 answers
37 views

Can a directed acyclic graph exhibit chaotic behavior?

I have a physics background with very little knowledge of graph theory, but a question arose related to directed acyclic graphs (DAGs) and I'm hoping to get hints towards an answer. Assume we have a ...
Capuchin's user avatar
0 votes
1 answer
40 views

Weaker notion of topological ordering for directed graphs

Let $G = (V,E)$ be a directed graph with $v \rightarrow w$ denoting an edge from $v$ to $w$. Now if $\le$ is a total order on $V$ then $\le$ is called topological order of $G$ if $v \rightarrow w$ ...
MKR's user avatar
  • 224
2 votes
2 answers
115 views

A tournament is acyclic if and only if it has no triangles

A tournament is a directed graph where between any two distinct vertices there is either the edge (u,v) or the edge (v,u) (one of them only). I have not come across a proper explanation on why the ...
Yavuz Bozkurt's user avatar
3 votes
1 answer
190 views

How many ways of traversing every arc of a complete digraph exactly once from a given starting vertex are there?

Given a set of $n$ states $V = \{ s_1, s_2, \ldots, s_n \}$, and a complete digraph $G = (V, A)$ where $A = \{ (a,b) \mid (a,b) \in V^2\; \text{and}\; a \neq b \}$, I'm interested in finding cyclic ...
Florian Ragwitz's user avatar
0 votes
1 answer
30 views

Calculation of Shortest Paths in a Directed Graph takes much longer than calculating Betweenness Centrality

First of all, I am trying to calculate the Betweenness Centrality of a fully connected directional graph with edge weights with N=3015 nodes. Matlab can do this in about 30 seconds and Python igraph ...
Dom's user avatar
  • 256
0 votes
1 answer
67 views

How many topological orders does the following directed acyclic graph have?

Q: How many topological orders does the following directed acyclic graph have? You may basically think of it as putting numbers on a $2\times 6$ table such that the number at the right or down is ...
Ualibek Nurgulan's user avatar
0 votes
0 answers
86 views

Approximating the trace of the power of a large adjacency matrix

The motivation for this question is counting cycles in directed graphs with millions of vertices. Given a large (not necessarily symmetric) adjacency matrix $A \in \{0, 1\}^{n \times n}$, where $n \...
Vezen BU's user avatar
  • 2,150
0 votes
0 answers
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 "...
Jens's user avatar
  • 119
0 votes
0 answers
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 ...
Eric Cochran's user avatar
1 vote
1 answer
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 ...
snofelet's user avatar
1 vote
0 answers
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(...
Smylic's user avatar
  • 7,016
0 votes
0 answers
52 views

Network flow - does edge lie on directed path

a) Let $f$ be a flow network $(G, c, s, t)$ and $e$ an edge such that $f(e) > 0$. Then there must exist a directed path from $s$ to $t$ that contains the edge $e$. b) Let $f$ be a flow network $(G, ...
popcorn's user avatar
  • 311
2 votes
1 answer
50 views

Name of the edge whose removal causes the graph to be weakly connected

Given a strongly connected digraph G, there exists an edge that, when removed, makes the graph weakly connected. What is this edge called?
lakdee's user avatar
  • 95
0 votes
1 answer
70 views

Determine if each of the following graphs is connected and/or super-connected. Briefly justify your responses. [closed]

I am struggling to answer this question, and I was hoping for some assistance and/or help, it would be greatly appreciated. This link is a screenshot of the question because it does include diagrams: ...
Ella's user avatar
  • 31
1 vote
1 answer
175 views

Can we have undirected edges and directed edges in a graph

Suppose there are 3 vertices in a graph. They are connected as a to b, b to a, b to c and a to c. Then, we can draw just a line without arrows between a and b as it has arrows in both directions and ...
Hasini's user avatar
  • 201
0 votes
1 answer
28 views

Counting row permutations that result in nonzero diagonals

Let $A$ be a binary square matrix in {$0,1$}$^{n\times n}$. What is the number of row permutations that will result in nonzero diagonals? I.e., the number of permutation matrices $P$ s.t. the diagonal ...
graphitump's user avatar
0 votes
0 answers
21 views

Find min-cost group-shared tree when the link weight is asymmetric

In sahasrabuddhe2000multicast's Cost Optimization section, it states that when the link weight is asymmetric, the problem of finding a minimum-cost group-shared multicast tree can be reduced to the ...
jhsheng's user avatar
1 vote
1 answer
31 views

Complete Directed Graph and Decision Theory

In decision theory, condition $ \beta $ is defined as follows: If $a,b \in A \subset B, a, b \in C(A)$, and $b \in C(B)$, then $a \in C(B) $. $C(.)$ here is the choice correspondence of a decision ...
sucksatmath's user avatar
0 votes
0 answers
37 views

Is there a name for this graph algorithm?

I have a Directed Acyclic Graph (it's causal, but that's actually not important for this question). Suppose I have the chain $A\to B\to C\to D.$ I want a row output consisting of all possible ancestor-...
Adrian Keister's user avatar
1 vote
1 answer
53 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 ...
CREATIVITY Unleashed's user avatar
0 votes
0 answers
38 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) ...
Shaggy's user avatar
  • 1
1 vote
1 answer
52 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$ ...
GaussJordan's user avatar
1 vote
1 answer
75 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 ...
Fabius Wiesner's user avatar
0 votes
0 answers
68 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 ...
a person's user avatar
0 votes
2 answers
154 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 ...
licheng's user avatar
  • 2,474
2 votes
1 answer
96 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 ...
Thomas B.'s user avatar
  • 187
0 votes
1 answer
43 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, ...
Keen's user avatar
  • 1,190
3 votes
0 answers
105 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. ...
ratatouille's user avatar
1 vote
1 answer
111 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 ...
bdrum's user avatar
  • 11
1 vote
0 answers
53 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 ...
Uri Greenberg's user avatar
1 vote
1 answer
101 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 ...
Salban Nithilaselvan's user avatar
0 votes
1 answer
184 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 ...
JayDew's user avatar
  • 13

1
2 3 4 5
9