# Questions tagged [directed-graphs]

A directed graph is a graph with directed edges. Loops and 2-cycles are usually allowed. See also the tag *quiver*.

105 questions
Filter by
Sorted by
Tagged with
44 views

### Kernel perfection in some powers of cycles

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
• 1,841
1 vote
105 views

### Misunderstanding the definition of kernel in digraphs

By Borodin–Kostochka–Woodall '97 paper, the first paragraph says that directed odd cycles do not have kernels. But, I don't get this. Like, consider any $\lfloor\frac{n}{2}\rfloor$ set of independent ...
• 1,841
1 vote
27 views

### Both-way flows in a directed graph

Let $G$ be a finite directed graph, and let $s,t$ be two distinct vertices. Problem $1(s,t)$. Find the maximum number of mutually edge-disjoint directed paths from $s$ to $t$. OK, I didn't think of ...
269 views

• 1,111
429 views

### Extension of Erdős-Gallai (s,t)-path theorem to directed graphs

The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498): Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
343 views

### Does a strong digraph always admit a vertex that lies on some path between $\Theta(n^2)$ pairs of vertices?

Let $G$ be a directed graph. Call a vertex $v$ in $G$ central if there exists $\Theta(n^2)$ distinct pairs of vertices $(u,w)$ such that $v$ lies on some path from $u$ to $w$. We do not care whether ...
1 vote
19 views

### Path cover with sets of nodes

I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...
1 vote
106 views

### Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
• 283
1 vote
101 views

### Lengths of paths through Conway’s Game of Life

This question is inspired by the following challenge from CodeGolf.SE: https://codegolf.stackexchange.com/q/251510/88765. Given positive integer $N$, we can consider a version of Conway’s game of life ...
• 2,744
75 views

### Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$

The last problem in 2022 IMC Day 1 strongly correlates with graph theory. In its official solution, the fundamental approach can be rephrased as follows. Give a digraph $G=(V,E)$. We call a subset of ...
1 vote
90 views

### Minimum edge-weighted directed subgraph in polynomial time

I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
103 views

### Digraph without "immediately isomorphic" vertices?

Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is ...
1 vote
53 views

• 941
1 vote
30 views

### Given a simple undirected graph, how to direct its edges to make it transitive

I am currently looking for an algorithm to determine whether we can direct every edge (no adding or deleting edges allowed) so that the graph is transitive (meaning that if (x,y) and (y,z) are edges ...
• 261
1 vote
886 views

### Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?

I am looking at doing some basic validation on a database of st-dags. It would be useful to have: A formula for the number of non-isomorphic st-dags with n vertices A formula for the same with n ...
• 21
109 views

### Are there any necessary conditions of the existence of a Hamiltonian cycle on directed graphs

I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems
144 views

### Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows: Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
• 71
119 views

• 2,765
464 views

### Directed graph minor theorems

In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition A directed graph is a minor of ...
94 views

### Has it already been shown that a digraph is $k$-connected if and only if there is a set of $k$ disjoint paths between every pair of vertices? [closed]

My question concerns graph theory. There is a conjecture I know to be true, but I am not sure whether it has been proven before. It is a fairly simple result. It may be well-known; I am not sure. ...
1 vote
204 views

### Expected number of directed cycle in a directed complete graph

Consider the randomized, directed complete graph G = (V, E) where for each pair of vertices u, v ∈ V, we add either the directed edge (u → v) or the directed edge (v → u) chosen uniformly at random. ...
1 vote
103 views

### Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
• 130
31 views

I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$. For example, $P_j=\left[f^{-j}(... • 23 2 votes 0 answers 270 views ### Terminology for transforming a directed acyclic graph into a tree I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree$> 1$. Such a ... • 255 2 votes 0 answers 160 views ### Discrete version of Helmholtz decomposition In The curl of graphs and networks (Gustafson and Haray, 1984) it is claimed to be shown that any digraph$G$can be decomposed as the sum of three graphs$U_1 + U_2 + U_3$, where$U_1$is divergence-... • 121 1 vote 1 answer 84 views ### Infinite directed paths in tournaments on$\omega$Does every tournament on$\omega$contain an infinite directed path that doesn't visit any vertex twice? 1 vote 1 answer 198 views ### Explicit upper bound on the number of simple rooted directed graphs on 𝑛 vertices? Harary mentioned this problem in "The number of linear, directed, rooted, and connected graphs" on p. 455, l. 3–5, but a short and crisp upper bound is missing. I believe that someone must ... 10 votes 1 answer 349 views ### When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of$3$-colorable perfect graphs? Call an oriented digraph$D=(V,A)$circular when for all$\small x,y,z\in V$if$(x,y)\in A$and$(y,z)\in A$then$(z,x)\in A$or equivalently if$D$is any oriented digraph whose arc set is a ... • 2,466 4 votes 2 answers 236 views ### Population of P people, where each person knows K others, how many people mutually know each other If you have a population of$P$people, where each person knows$K$others within the population (does not have to be mutual, i.e., if I know you, you don't necessarily know me), and$1<K<P$, ... 4 votes 1 answer 194 views ### Characterizing relations by forbidden induced subsets Working with relations in a purely set theoretic manner i.e. as just sets of ordered pairs, we see for any relation$R$there exists unique inclusion minimal sets$A$and$B$such that$R\subseteq A\...
• 2,466
1 vote
Given an asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for all arcs $\alpha\in A$ the digraph $D−\alpha=(V,A\setminus\{\alpha\})$ is ...