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

66 questions
Filter by
Sorted by
Tagged with
57 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. ...
61 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 ...
13 views

68 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 ...
42 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-...
44 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?
129 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 have ...
206 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 ...
206 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$, ...
178 views

91 views

### Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute. Two complex matrices $A$ and $B$ are said to be unitary similar if ...
167 views

### Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph

I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they ...
99 views

### The properties of almost all directed graphs

A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
137 views

### Frobenius normal form of a doubly stochastic matrix

If $A \in M_n(\mathbb{C})$, then $A$ is called reducible if there is a permuation matrix $P$ such that $$P^\top A P = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix},$$ in ...
109 views

### Latent Dirichlet allocation and properties of digamma function

In the paper Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent Dirichlet Allocation. Journal of Machine Learning Research, 3(4–5), 993–1022. http://www.jmlr.org/papers/volume3/blei03a/blei03a....
45 views

### Proof of the asymptotic expression for the number of self-converse digraphs?

The following expression was mentioned in the master thesis of Alastair Farrugia on Page 199 of his thesis Self-complementary graphs and generalisations: a comprehensive reference manual, M.Sc. Thesis,...
45 views

### Groups that can occur as graph automorphisms of a fixed size graph

From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's ...
36 views

246 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?
222 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$ ...
71 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 ...
86 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 front end and rear ...
81 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 ...
255 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 ...
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 ...
101 views

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)... 0answers 161 views ### Similarities between isomorphism classes of homeomorphic directed graphs 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 ... 1answer 55 views ### Orientations in connected bridgeless graphs Let$n\geq 3$be an integer, set$[n] = \{1,\ldots,n\}$and let$G=([n],E)$be an undirected connected bridgeless graph. Is there an orientation (explanation below) of$G$such that for all$a\neq b\...
Every tournament contains a directed Hamiltonian path (a path visiting every vertex exactly once). Suppose that $T$ is a tournament on $[n]:=\{1,\ldots,n\}$ for some integer $n\geq 2$ with exactly ...