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.
439 questions
0
votes
0
answers
12
views
Seeking resources about multiple directed acyclic graphs/topological orderings
I'm modeling knowledge as consisting of two pieces: the content itself, which we can call Nouns (N), and things you can do with that content, which we can call Verbs (V). For each of the collections ...
- 1
2
votes
2
answers
93
views
Does every poset arise as the reachability relation of some DAG?
Let $G=\left(V,E\right)$ be a directed acyclic graph (DAG). Define a relation $\preceq$ on $V$ by
$$a\preceq b \iff \text{there exists a directed walk from $a$ to $b$}$$
(If needed, allow the length-0 ...
- 47
0
votes
0
answers
29
views
Looking for a reference for node contraction in directed graphs
Given a digraph $G'$ and a node $v \in V(G')$, define the contraction of node $v$ as follows.
Let $u_1, u_2, \ldots, u_p$ be the in-neighbours of $v$ and $w_1, w_2, \ldots, w_q$ be the out-neighbours ...
- 530
0
votes
0
answers
36
views
Which blockers are there in a $(2,2)$-regular directed graph to have an edge disjoint cycle cover
Consider a $(2,2)$-regular simple directed graph $G$, i.e., if $(v,w)$ is an edge, $(w,v)$ is not. I was wondering if there is always a set of edge disjoint cycles $C$ in $G$ such that each vertex is ...
- 1,113
2
votes
1
answer
35
views
A, B closed walks; A $\subset$ B; is A-B union of cycles or something else?
Let $D$ be a directed graph with no multi edge (but 2-cycles are allowed). Let $A$ be a closed walk on $D$; and $D'$ be the graph spanned by $A$; aka $D'$ contains all nodes and arcs visited by $A$ ...
- 619
0
votes
0
answers
30
views
Given DAG with $d$ levels, what is the min number of edges one needs to remove so that component containing source has at most $s$ levels?
Given single source directed acyclic graph (DAG) $G$ with $d$ levels and $m$ edges, what is the minimum size of a set of edges $S$ one needs to remove so that the component of the resulting graph $G \...
- 530
0
votes
1
answer
43
views
Constructing an edge-disjoint directed graph under certain conditions
I ran into this problem while working and was wondering whether it's even possible to solve.
Is it possible to construct a directed graph $G$ such that:
There are at least 4 nodes labelled $A$, $B$, $...
- 150
0
votes
1
answer
51
views
Strongly connected after reversing edges of a vertex in a strongly connected tournament
This is my question:
Let $T$ be a strongly connected tournament. Prove that there exists at least one vertex $v$ such that, if you reverse the direction of every arc incident with $v$, the resulting ...
3
votes
1
answer
101
views
Some unclear definitions in directed graphs
I was reading a very recent paper. There are some notions with which I am not familiar, and I am struggling to fully understand them - particularly the notions of connected digraph, and cut and dijoin ...
user1671795
1
vote
1
answer
17
views
Positivity of multiplicative path weights of directed acyclic graph when parent weights sum up to 1
Consider a weighted directed acyclic graph (DAG) with ajacency matrix $A=(A_{ij})_{1\le i,j\le n}$. Suppose the DAG has a single root node 1 (thus node 1 reaches every other node) and $\sum_{i=1}^n A_{...
- 953
1
vote
1
answer
73
views
A special property about functions on directed abelian groups
Let $\Lambda = (\Lambda,+,\leq)$ be a directed, torsion-free abelian group (that is, $\Lambda$ is a torsion-free abelian group together with a partial group ordering $\leq$ such that every two ...
- 83
0
votes
1
answer
34
views
Given a directed graph $D$. Suppose $S$ is a minimal set such that $N^-(S)$ is a subset of $N^+(S)$, does this imply that $S$ is contained in a cycle?
Let $D$ be a directed graph, and suppose that $S\subset V(D)$ is a minimal subset of size at least two such that $N^-(S)\subset N^+(S)$. Does this "domination" condition imply that $S$ is ...
- 1
0
votes
0
answers
75
views
How to solve ${\bf Q} {\bf x} = {\bf 0}_n$ subject to ${\bf x} > {\bf 0}_m$ and costing less than $\mathcal O (n^2)$?
Let $\bf Q$ be the oriented incidence matrix of a strongly connected digraph $\mathcal G := (\mathcal V, \mathcal E)$ that admits neither parallel edges nor self loops but allows for antiparallel ...
1
vote
1
answer
118
views
Determining the graph Laplacian of a digraph from incidence-like matrices
This question isn’t necessarily about Laplacian matrices!
Given the incidence matrix $B_S$ of an undirected graph $S$, we can calculate $B_SB_S^T=D_S-A_S$, where $D_S$ and $A_S$ are the degree and ...
- 57
-1
votes
1
answer
90
views
A directed graph with strange covers
I have a directed graph satisfying the following conditions.
1 For every node, the in-degree is at least one.
2 For every node, the out-degree is at least one
3 For every node, there exists a
...
- 541