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*.
41
questions with no upvoted or accepted answers
10
votes
0
answers
431
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 ...
8
votes
0
answers
438
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 ...
6
votes
0
answers
183
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 ...
6
votes
0
answers
125
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) &...
6
votes
0
answers
114
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 ...
6
votes
0
answers
69
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 ...
4
votes
0
answers
290
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)) =...
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 (...
4
votes
0
answers
244
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$ ...
4
votes
0
answers
193
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 ...
3
votes
1
answer
255
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....
3
votes
0
answers
53
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
0
answers
82
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 ...
3
votes
0
answers
113
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 ...
3
votes
0
answers
191
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
30
views
Do digraphs with "other" symmetries have interesting properties
Question:
do digraphs $G(V,A)$, whose adjacency matrix exhibits certain symmetries, have mathematically interesting properties?
The most famous such symmetry is $(i,j)\in A\iff(j,i)\in A$ for which ...
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
294
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
177
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-...
2
votes
0
answers
951
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?
2
votes
0
answers
168
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
117
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
31
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 ...
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 $...
1
vote
0
answers
26
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
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
50
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 ...
1
vote
0
answers
31
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
0
answers
75
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 ...
1
vote
0
answers
144
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 ...
1
vote
0
answers
101
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 ...
1
vote
0
answers
208
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
0
answers
110
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
0
answers
104
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, ...
1
vote
0
answers
237
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
49
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....
0
votes
0
answers
45
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
41
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 ...
0
votes
0
answers
106
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 ...
0
votes
0
answers
115
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
0
votes
0
answers
116
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” (...