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
0
votes
0answers
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. ...
1
vote
1answer
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 ...
0
votes
0answers
13 views
Find maximum directed graph
For a directed graph $G=(V,E)$, we want to compute the max number $k$ such that there exists a directed graph $H=(V,E')$ such that $E'\subseteq V\times V$ and $|E'|=k$ such that
For any $v\in V$, $(v,...
2
votes
0answers
19 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}(...
1
vote
0answers
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 ...
1
vote
0answers
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-...
1
vote
1answer
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?
1
vote
1answer
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 ...
9
votes
1answer
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 ...
4
votes
2answers
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$, ...
4
votes
1answer
178 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
2answers
73 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 ...
9
votes
0answers
382 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 ...
0
votes
0answers
21 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
0answers
90 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
1answer
99 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
1answer
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 ...
0
votes
1answer
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 ...
6
votes
0answers
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 ...
4
votes
2answers
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 ...
1
vote
1answer
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....
1
vote
0answers
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,...
3
votes
0answers
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 ...
3
votes
1answer
36 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
1answer
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
1answer
67 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
0answers
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?
3
votes
1answer
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$ ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
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 ...
3
votes
2answers
101 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
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 ...
0
votes
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\...
3
votes
1answer
444 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
1answer
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
1answer
79 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
2answers
231 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
2answers
347 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
1answer
120 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
1answer
608 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
0answers
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
4answers
813 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
1answer
231 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
1answer
2k 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
3answers
225 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
1answer
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
1answer
224 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 ...
