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

57
questions

**3**

votes

**1**answer

147 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

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

**2**

votes

**0**answers

50 views

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

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...

**0**

votes

**0**answers

17 views

### Twisted Laplace eigenvalues on graph

Let $X$ be a regular finite connected graph and $\Gamma$ its fundamental group.
Fix a character $\chi:\Gamma\to\mathbb{C}^\times$.
This defines a locally constant sheaf on $X$ and there is an ...

**1**

vote

**0**answers

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

**1**

vote

**1**answer

91 views

### Characterisation of walk-equivalent digraphs

Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$,
$\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...

**2**

votes

**1**answer

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

**0**

votes

**1**answer

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

**6**

votes

**0**answers

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

**3**

votes

**2**answers

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**1**answer

32 views

### Finite sequences realizable by degree difference in digraphs

Let $n>0$ be an integer, and let $[n] = \{1,\ldots,n\}$. A function $f:[n]\to \mathbb{Z}$ is said to be in- and out-degree-realizable (or io-realizable for short) if there is a directed graph $G = (...

**6**

votes

**1**answer

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

**1**

vote

**1**answer

60 views

### Algorithm generating digraphs

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

**2**

votes

**0**answers

165 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?

**3**

votes

**1**answer

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

**3**

votes

**0**answers

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

**0**

votes

**1**answer

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

**3**

votes

**1**answer

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

**3**

votes

**2**answers

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

**3**

votes

**1**answer

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

**3**

votes

**2**answers

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

**4**

votes

**0**answers

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

**0**

votes

**1**answer

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

**3**

votes

**1**answer

414 views

### Tournaments with exactly one directed Hamiltonian path

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

**1**

vote

**1**answer

83 views

### Sum-coloring a tournament

If $G=(V,E)$ is a loopless finite directed graph and $v\in V$, we set $\text{In}(v) = \{(w,v): w\in V \land (w,v) \in E\}$.
Let $T=(V,E)$ be a tournament such that for every $v\in V$ the set $\text{...

**6**

votes

**1**answer

75 views

### Characterizing SP-DAGs by Forbidden Minors?

So it's well-known that an alternative way to define a series-parallel (undirected graph) is by the forbidden minor $K_4$. Is there a known analog of this definition for directed graphs — ...

**5**

votes

**2**answers

222 views

### Graph isomorphism problem for minimally strongly connected digraphs

A minimally strongly connected digraph (MSC) is strongly connected (SC), while removal of any arc destroys this. That is, between any two vertices a, b there exists a directed path from a to b, while ...

**4**

votes

**2**answers

336 views

### What Kind of Graph is This?

I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.
The overarching rationale is that the reduction is done via a sequence of ...

**0**

votes

**1**answer

119 views

### Length of longest directed circuit in random tournament

Build a random tournament $T=(V,E)$ on $V=\{1,\ldots, n\}$ in the following fashion: for $i < j\in \{1,\ldots, n\}$ let the probability be $0.5$ whether $(i,j)\in E$ or $(j,i)\in E$ (in a ...

**3**

votes

**1**answer

548 views

### Is transitive reduction for a direct acyclic graph really unique? [closed]

According to Wikipedia, "If a given graph is a finite directed acyclic graph, its transitive reduction is unique"
Here is what I think might be a counter-example:
Imagine a diamond-shaped DAG where
...

**1**

vote

**0**answers

95 views

### Generating tournaments inductively

This is a somewhat vague question, but I'm interested in ways to create a strong tournament from one or more smaller tournaments. Obviously, the disjoint union of two tournaments is a new tournament, ...

**6**

votes

**4**answers

775 views

### Minimum negative eigenvalue of zero-one matrices

The following question must have been answered decades ago.
For $n$ fixed, what is the most negative eigenvalue among all trace zero zero-one matrices (that is, all entries are either zero or one, ...

**5**

votes

**1**answer

218 views

### The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$

For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...

**3**

votes

**1**answer

1k views

### Removing cycles in a directed graph by swapping edges orientation

I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v_i$ and $E$ (directed) edges $e_j$. I know that if an edge $e_k = (v_i, v_j)$ is in the graph, then the opposite ...

**4**

votes

**3**answers

209 views

### Name for directed graphs with “balanced cycles”

Does the following class of graphs have a name?
I'm interested in directed graphs with the following property: for every cycle (of the underlying undirected graph) half of the edges go in one ...

**8**

votes

**1**answer

1k views

### The number of Hamiltonian paths in a tournament

If $h(T)$ denotes the number of (directed) Hamiltonian paths in the tournament $T,$ what is the range of $h(T)$ as $T$ ranges over all (finite) tournaments $T$?
By a classical theorem of Rédei [...

**5**

votes

**1**answer

216 views

### Directed homotopy in the Cayley graph of a monoid

There is a the notion of the Cayley graph $C(G)$ of a group $G$ (which depends on a given presentation $G \cong \mathcal F(S) / \sigma$ where $\mathcal F$ is the free group functor and $\sigma$ some ...

**9**

votes

**1**answer

178 views

### A generalisation of $C_0$-semigroups

A $C_0$-semigroup is a strongly continuous family $\{T(t)\}$ of bounded linear operators on a normed space $X$, indexed in $\mathbb R_+$ and with two additional properties that make it look like an ...

**3**

votes

**0**answers

104 views

### Does this notion of “$\mathcal{F}$-digraph” appear in the literature?

By a digraph, I mean a quiver with no multiple edges. So in particular:
Loops are okay.
An infinite set of vertexes is okay.
Furthermore, I will tend to identify each digraph with its underlying set ...

**5**

votes

**0**answers

62 views

### Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...

**5**

votes

**1**answer

701 views

### How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different ...

**0**

votes

**1**answer

229 views

### Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...

**2**

votes

**0**answers

161 views

### Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.
Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$.
From ...

**2**

votes

**0**answers

159 views

### When does the induced directed graph of a directed multigraph preserve information?

Let G be a directed multigraph, and let H be the induced directed graph whose vertices are the edges of G, and whose edges are given by pairs of consecutive edges in G; i.e., there is an edge from v ...

**1**

vote

**0**answers

221 views

### Inverse (in)degree of a digraph

Hi All,
here is my question. I'm given a directed graph $(V,E)$ with $|V| = n$ vertices and in-degrees $d_1$, $d_2$ ... $d_n$ (so that $\sum_i d_i = |E|$). Can we upper bound the inverse (in)degree ...

**0**

votes

**0**answers

89 views

### “Box Nodes” in Directed Graphs with Paired IO Symmetry

Consider directed graphs where all nodes have 2 inputs and 2 outputs. If we
design a box with N inputs and N outputs, what is the smallest number of
nodes it must contain to satisfy “pair symmetry” (...

**14**

votes

**0**answers

512 views

### A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?

Maybe I am missing something, but found potential counterexample to a conjecture
of Nash-Williams.
According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS
The outdegree and indegree sequences of ...