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
Filter by
Sorted by
Tagged with
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 ...
Ethan Splaver's user avatar
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 ...
Nicole Wein's user avatar
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 ...
Gordon Royle's user avatar
  • 12.3k
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) &...
Alt-Tab's user avatar
  • 139
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 ...
Aidan Rocke's user avatar
  • 3,827
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 ...
Brendan McKay's user avatar
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)) =...
Alexander's user avatar
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 (...
Daniel Krenn's user avatar
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$ ...
Yonathan Touati's user avatar
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 ...
Ethan Splaver's user avatar
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....
sunxd's user avatar
  • 191
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Dominic van der Zypen's user avatar
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 ...
goblin GONE's user avatar
  • 3,693
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 ...
Manuel Lafond's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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}(...
bmf's user avatar
  • 23
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 ...
Dudi Frid's user avatar
  • 255
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-...
Jsevillamol's user avatar
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?
user92158's user avatar
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 ...
Ben's user avatar
  • 167
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Brendan McKay's user avatar
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 $...
Oleksandr  Kulkov's user avatar
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 ...
Andres Fielbaum's user avatar
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 ...
alosc's user avatar
  • 71
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 ...
Salomo's user avatar
  • 121
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 ...
Karthik C's user avatar
  • 261
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 ...
Jan Westerdiep's user avatar
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 ...
user115415's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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. ...
John Cartor's user avatar
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 \...
Sirolf's user avatar
  • 493
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, ...
coolpapa's user avatar
  • 455
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 ...
Claudio Gentile's user avatar
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....
vidyarthi's user avatar
  • 2,007
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$ ...
Jens Fischer's user avatar
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 ...
Oleksandr  Kulkov's user avatar
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 ...
Zach Hunter's user avatar
  • 3,393
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
Anđela Todorović's user avatar
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” (...
bobuhito's user avatar
  • 1,537