# 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

0
votes

0
answers

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
vote

0
answers

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
vote

0
answers

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

4
votes

0
answers

269
views

### What is the geometric interpretation of the first Hochschild homology group of path algebra constructed from a directed graph?

Let $\mathcal{G} = (V, E, s, t)$ is a directed graph, where $V$ - the set of its vertices, $E$ - the set of its edges, $s: E \rightarrow V, s((v_1, v_2)) = v_1$ and $t: E \rightarrow V, s((v_1, v_2)) =...

0
votes

0
answers

41
views

### Maximal family of cycles in directed 3-regular graphs

Consider a finite directed 3-regular graph $G=(V,E)$ where $(v,w)\in E$ implies also that $(w,v)\in E$. I am looking for a maximal set $\mathcal{C}$ of simple cycles of length greater of equal $3$ ...

0
votes

0
answers

38
views

### Enumerating directed cacti by the number of vertices and edges

Let's say that a directed cactus is a labeled directed graph, such that each vertex belongs to at most one simple cycle. In other words, it is a directed graph such that all its strongly connected ...

1
vote

0
answers

38
views

### Probability of generating the same DAG after picking a topological ordering 3 times in a row

Consider the following process:
Choose a random permutation $p$ of $\{1, 2, \dots, n\}$ out of $n!$ options.
Choose a random directed acyclic graph $G$ that has $p$ as a topological ordering out of $...

8
votes

0
answers

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

9
votes

2
answers

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

0
answers

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

1
answer

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

1
vote

0
answers

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
votes

1
answer

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

2
answers

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

3
votes

1
answer

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

1
answer

53
views

### Generate all strongly connected tournament

I want to generate all strongly connected tournament of size $n \in \{4, 11\}$.
As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n ...

6
votes

0
answers

153
views

### Maximum number of Hamilton paths in a tournament on $n$ vertices

Recall that a tournament is a directed graph $T$ such that for every pair of distinct vertices $\{v,w\}$, exactly one of the ordered pairs $(v,w)$, $(w,v)$ is an arc of $T$.
A tournament is strongly ...

1
vote

0
answers

61
views

### Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree

Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...

1
vote

0
answers

48
views

### Reference for a lemma on acyclic subgraph

Lemma. Let $D$ be a digraph. Then there exists an acyclic subdigraph $D'$ of $D$ such that the total degree (i.e. out-degree plus in-degree) of $v$ in $D'$ is at least the out-degree of $v$ in $D$ for ...

4
votes

0
answers

59
views

### Graph-class defined by matrix-like vertex-operations

Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices
$$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$
and edges as follows:
$(i,j) \in V$ is adjacent (...

2
votes

1
answer

136
views

### Is the set of "endomorphisms" of a directed set again a directed set?

Let $(I,\leq)$ be a directed set, that is $\leq$ is reflexive and transitive and for every $a,b\in I$ we find $c\in I$ such that $a,b\leq c$. Now consider the set $M$ consisting of all maps $\sigma:I\...

1
vote

0
answers

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

1
vote

2
answers

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

0
votes

0
answers

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

2
votes

1
answer

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

6
votes

0
answers

119
views

### Minimum of sums over degree products in a directed acyclic graph

My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) &...

4
votes

1
answer

245
views

### Dominating sets in subtournaments of the Paley tournament

For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...

8
votes

1
answer

292
views

### Does the random graph interpret the random directed graph?

The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary ...

3
votes

1
answer

333
views

### Convergence on iterating a piecewise function

Given the four functions $P_1$, $P_2$, $N_1$ and $N_2$ (which together is a piecewise function) each with domain and range as shown above:
Is there an explanation as to why starting at any integer (...

1
vote

0
answers

74
views

### Name for a directed acyclic graph with no skip-level edges?

I'm looking at a specific class of DAGs, namely those DAGs such that any path from $u$ to $v$ has the same length. Informally, we don't allow "skip-level" edges. I understand these graphs ...

3
votes

2
answers

2k
views

### Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

I have a two part question:
Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...

1
vote

0
answers

132
views

### Infinite recursive graphs and different ways to build them

I asked this question one week ago on MSE and has received no answer.
Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications.
They can be ...

3
votes

1
answer

200
views

### Using a poset or directed graph as input for a neural network

I'm not sure if this is the right community to post this in but I would appreciate any help. As the title states, I'm trying to train a neural network using some unconventional input. I'm wondering if ...

1
vote

0
answers

99
views

### Kernel perfect orientations of complete graphs

How can we create a kernel perfect orientation of a complete graph? A kernel of a graph is a set of vertices in a graph $G$, which absorbs other vertices, that is, has all the vertices in its ...

3
votes

2
answers

215
views

### Digraphs with exactly one Eulerian tour

I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...

4
votes

1
answer

173
views

### Digraphs with unique walk of length $k$ between any two vertices

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices.
Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...

6
votes

1
answer

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

0
votes

1
answer

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

0
answers

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

1
answer

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

2
votes

0
answers

31
views

### On the number of connected functional digraphs recoverable from the preimage set size structure

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}(...

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

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

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

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

1
vote

2
answers

1k
views

### Finding the max-value set of cycles in a weighted digraph

I am looking for the most efficient algorithm that can solve this problem:
Given a directed graph with real-valued edge weights, find a set of directed cycles (no two cycles can share a vertex) that ...

10
votes

0
answers

427
views

### When does a graph have a minimally strong orientation?

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