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

79 questions
Filter by
Sorted by
Tagged with
113 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 ...
65 views

125 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 ...
59 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. ...
72 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. ...
66 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 ...
25 views

391 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 ...
401 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 ...
93 views

### Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs. Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that \...
105 views

118 views

### Non-equivalent eulerian trails in $K_{2n+1}$

Two eulerian trails of $K_{2n+1}$ are defined to be equivalent if the orientations obtained by orienting the edges as traversed by the trails are isomorphic as digraph. How many non-equivalent trails ...
79 views

Is there an algorightm generating all digraphs with $n$ edges up to isomorphism whose underlying graph is not a tree? For example, for $n=3$, there are only two such digraphs, representable as $\text{... 0answers 428 views ### Algorithms for rooted directed acyclic graph isomorphism Given two directed acyclic graphs$G_1$and$G_2$, and their roots$r_1$and$r_2$, is there a polynomial algorithm to determine if$G_1$and$G_2$are isomorphic? 1answer 224 views ### Does every directed graph have a directed coloring with$4$colors? Every finite directed graph has a majority coloring with$4$colors. (The notion of majority coloring is defined below.) Question. Can every infinite directed graph be majority-colored with$4$... 0answers 77 views ### Decreasing the directed chromatic number of a digraph by adding an edge The chromatic number of an undirected graph can never be decreased by adding an edge. However, things are not that clear when we deal with coloring directed graphs - but first, the definition of this ... 1answer 89 views ### Name for Directed Edges in Digraphs Graph theory originated in German speaking countries and there directed edges are called "Pfeil" which translates to "arrow", which makes sense, because arrows have distinguishable ... 1answer 85 views ### Generalized digraph homomorphisms and graph cores Given any digraphs$G$and$H$we say a surjection$f:V(G)\to V(H)$reduces$G$to$H$if and only if it satisfies$(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ... 0answers 203 views ### Blocking directed paths on a DAG with a linear number of vertex defects Let$G=(V,E)$be a directed acyclic graph. Define the set of all directed paths in$G$by$\Gamma$. Given a subset$W\subseteq V$, let$\Gamma_W\subseteq \Gamma$be the set of all paths in$\Gamma$... 2answers 256 views ### Orientability of$\mathbb{Z}^n$For any set$X$set$[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If$n\geq 2$is an integer, we endow$\mathbb{Z}$with a graph structure in the following way. If$x,y\in \mathbb{Z}^n$we say$x,y$are ... 1answer 96 views ### an inverse semigroup (and perhaps a$C^*\!$-algebra) associated with a directed graph The following inverse semigroup associated to a directed graph came up in my research. I've read that from an inverse semigroup one may derive a$C^*\!$-algebra whose generators are partial isometries ... 2answers 105 views ### In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop? Given any relation$R$, that is, any set of ordered pairs, we can associate a unique digraph$D$to our relation$R$by setting$D=(\text{fld}(R),R)$where$\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by ...