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*.
111
questions
4
votes
2
answers
237
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
200
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,506
1
vote
2
answers
1k
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
432
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,506
1
vote
0
answers
111
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
\...
- 493
1
vote
1
answer
136
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)...
- 493
2
votes
1
answer
118
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 ...
- 493
1
vote
1
answer
1k
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 ...
- 13
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 ...
- 3,827
4
votes
2
answers
401
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,711
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....
- 191
1
vote
1
answer
78
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,...
- 437
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 ...
- 13.7k
3
votes
1
answer
46
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 = (...
- 45.5k
6
votes
1
answer
132
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,034
1
vote
1
answer
170
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
2
votes
0
answers
959
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?
- 21
3
votes
1
answer
268
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$ ...
- 45.5k
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 ...
- 45.5k
0
votes
1
answer
104
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 ...
- 12.7k
3
votes
1
answer
94
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 ...
- 2,506
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$ ...
- 141
3
votes
2
answers
269
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 ...
- 45.5k
3
votes
1
answer
119
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 ...
- 369
3
votes
2
answers
136
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)...
- 2,506
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 ...
- 2,506
0
votes
1
answer
65
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\...
- 45.5k
3
votes
1
answer
915
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 ...
- 45.5k
1
vote
1
answer
88
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{...
- 45.5k
6
votes
1
answer
106
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 — ...
7
votes
2
answers
315
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
410
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 ...
- 12.7k
15
votes
3
answers
600
views
Maximum matching in a graph with no "shortcuts"
For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...
- 30.7k
1
vote
1
answer
164
views
Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle ...
0
votes
1
answer
160
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 ...
- 45.5k
3
votes
1
answer
815
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
...
- 133
1
vote
0
answers
105
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, ...
- 455
7
votes
4
answers
1k
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, ...
- 4,669
5
votes
1
answer
407
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 ...
- 11.9k
5
votes
1
answer
3k
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 ...
- 53
4
votes
3
answers
372
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 ...
- 489
12
votes
1
answer
2k
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 (...
- 11.9k
5
votes
1
answer
277
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 ...
- 190
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,693
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 ...
- 37.2k
5
votes
1
answer
1k
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 ...
- 2,175
0
votes
1
answer
331
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 ...
- 1
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 ...
- 270
11
votes
5
answers
1k
views
Which directed graphs have a normal adjacency matrix?
I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
- 3,679
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 ...
- 167