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*.
92
questions
1
vote
2
answers
62
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 13
3
votes
0
answers
81
views
Digraph without "immediately isomorphic" vertices?
Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is ...
- 393
1
vote
1
answer
32
views
Generate all strongly connected tournament
I want to generate all strongly connected tournament of size $n \in \{4, 11\}$.
As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n ...
- 75
6
votes
0
answers
87
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 ...
- 10.8k
1
vote
0
answers
36
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 ...
- 31
1
vote
0
answers
42
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 ...
- 121
0
votes
0
answers
28
views
Regrouping the leaf nodes of the WordNet DAG
Motivation
I am trying to find a criterion to regroup the classes of the ImageNet challenge dataset, one of the most important datasets used in Machine Learning.
The ImageNet dataset has 1000 classes ...
4
votes
0
answers
57
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 (...
- 567
2
votes
1
answer
129
views
Is the set of "endomorphisms" of a directed set again a directed set?
Let $(I,\leq)$ be a directed set, that is $\leq$ is reflexive and transitive and for every $a,b\in I$ we find $c\in I$ such that $a,b\leq c$. Now consider the set $M$ consisting of all maps $\sigma:I\...
- 805
1
vote
0
answers
27
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 ...
- 261
1
vote
2
answers
385
views
Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?
I am looking at doing some basic validation on a database of st-dags. It would be useful to have:
A formula for the number of non-isomorphic st-dags with n vertices
A formula for the same with n ...
- 21
0
votes
0
answers
50
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
2
votes
1
answer
132
views
Directed version of this lemma
On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
- 31
6
votes
0
answers
90
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) &...
- 119
4
votes
1
answer
160
views
Dominating sets in subtournaments of the Paley tournament
For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...
- 1,461
8
votes
1
answer
241
views
Does the random graph interpret the random directed graph?
The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary ...
- 1,579
3
votes
1
answer
250
views
Convergence on iterating a piecewise function
Given the four functions $P_1$, $P_2$, $N_1$ and $N_2$ (which together is a piecewise function) each with domain and range as shown above:
Is there an explanation as to why starting at any integer (...
- 143
1
vote
0
answers
63
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 ...
- 111
3
votes
2
answers
797
views
Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected
I have a two part question:
Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...
- 1,461
1
vote
0
answers
93
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 ...
- 161
0
votes
1
answer
111
views
Using a poset or directed graph as input for a neural network [closed]
I'm not sure if this is the right community to post this in but I would appreciate any help. As the title states, I'm trying to train a neural network using some unconventional input. I'm wondering if ...
1
vote
0
answers
59
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,611
3
votes
2
answers
194
views
Digraphs with exactly one Eulerian tour
I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...
- 31
4
votes
1
answer
138
views
Digraphs with unique walk of length $k$ between any two vertices
Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices.
Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...
- 1,663
5
votes
1
answer
252
views
Directed graph minor theorems
In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition
A directed graph is a minor of ...
- 592
0
votes
1
answer
69
views
Has it already been shown that a digraph is $k$-connected if and only if there is a set of $k$ disjoint paths between every pair of vertices? [closed]
My question concerns graph theory.
There is a conjecture I know to be true, but I am not sure whether it has been proven before. It is a fairly simple result. It may be well-known; I am not sure.
...
- 111
1
vote
0
answers
139
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. ...
- 19
1
vote
1
answer
76
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 ...
- 130
2
votes
0
answers
28
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}(...
- 23
1
vote
0
answers
164
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 ...
- 235
2
votes
0
answers
120
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-...
- 121
1
vote
1
answer
60
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?
- 39.4k
1
vote
1
answer
177
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 ...
user151154
10
votes
1
answer
256
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 ...
- 2,371
4
votes
2
answers
224
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
1
answer
190
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\...
- 2,371
1
vote
2
answers
725
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 ...
- 21
10
votes
0
answers
412
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 ...
- 2,371
1
vote
0
answers
94
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
\...
- 443
1
vote
1
answer
111
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)...
- 443
2
votes
1
answer
106
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 ...
- 443
0
votes
1
answer
478
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 ...
- 3
6
votes
0
answers
105
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,203
4
votes
2
answers
231
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,673
1
vote
1
answer
182
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....
- 161
1
vote
1
answer
72
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,...
- 375
3
votes
0
answers
51
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 ...
- 12.8k
3
votes
1
answer
38
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 = (...
- 39.4k
6
votes
1
answer
125
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,004
1
vote
1
answer
126
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{...
- 81