All Questions
Tagged with graph-theory directed-graphs
90 questions
16
votes
1
answer
696
views
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
Maybe I am missing something, but found potential counterexample to a conjecture
of Nash-Williams.
According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS
The outdegree and indegree sequences of ...
- 25.4k
15
votes
3
answers
613
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^...
- 34.3k
13
votes
1
answer
8k
views
How can you compute the number of topological sorts in a DAG?
If you have a directed acyclic graph (DAG) $G$, a topological sort is just an ordering of the vertices such that if an edge $x \to y$ exists in $G$, then the index of $x$ is less than the index of $y$....
- 231
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 (...
- 13.4k
11
votes
5
answers
2k
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,699
10
votes
1
answer
370
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,506
10
votes
0
answers
438
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
9
votes
2
answers
363
views
Does a strong digraph always admit a vertex that lies on some path between $\Theta(n^2)$ pairs of vertices?
Let $G$ be a directed graph.
Call a vertex $v$ in $G$ central if there exists $\Theta(n^2)$ distinct pairs of vertices $(u,w)$ such that $v$ lies on some path from $u$ to $w$. We do not care whether ...
- 235
8
votes
0
answers
459
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 ...
- 81
7
votes
2
answers
324
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 ...
6
votes
1
answer
610
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 ...
- 612
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
6
votes
1
answer
124
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 — ...
6
votes
0
answers
218
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 ...
- 12.7k
6
votes
0
answers
130
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) &...
- 184
6
votes
0
answers
116
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,871
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.7k
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,205
5
votes
1
answer
386
views
Are directed graphs with out-degree exactly 2 strongly connected with probability 1?
Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not ...
- 6,969
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
5
votes
1
answer
423
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 ...
- 13.4k
5
votes
1
answer
162
views
When can we make a digraph acyclic by fliping groups of arcs?
We have a digraph D=(V,A) and its arc set A is partitioned into classes. We can flip the classes, which means changing the direction of all the arcs in the class.
Is there any result on when can we ...
- 286
4
votes
2
answers
239
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
2
answers
418
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 ...
- 13.2k
4
votes
3
answers
390
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 ...
- 499
4
votes
1
answer
208
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
4
votes
1
answer
273
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,701
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 (...
- 577
4
votes
0
answers
251
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
4
votes
0
answers
200
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
3
votes
2
answers
271
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 ...
- 48.9k
3
votes
1
answer
1k
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 ...
- 48.9k
3
votes
2
answers
138
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
3
votes
1
answer
173
views
Subset of the vertices in a tournament
Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the ...
- 169
3
votes
1
answer
274
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$ ...
- 48.9k
3
votes
1
answer
103
views
Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$
The last problem in 2022 IMC Day 1 strongly correlates with graph theory. In its official solution, the fundamental approach can be rephrased as follows.
Give a digraph $G=(V,E)$. We call a subset of ...
3
votes
2
answers
2k
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,701
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
3
votes
1
answer
845
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
3
votes
2
answers
233
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
3
votes
1
answer
374
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
3
votes
1
answer
108
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 ...
- 423
3
votes
0
answers
346
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 ...
- 265
3
votes
1
answer
283
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
3
votes
0
answers
56
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.9k
3
votes
0
answers
83
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 ...
- 48.9k
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,793
3
votes
0
answers
199
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
2
votes
1
answer
228
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible ...
- 13.2k
2
votes
1
answer
122
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