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*.

Filter by
Sorted by
Tagged with
16 votes
1 answer
687 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 ...
joro's user avatar
  • 24.2k
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^...
Max Alekseyev's user avatar
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 (...
bof's user avatar
  • 11.5k
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
1 vote
1 answer
135 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)...
Sirolf's user avatar
  • 493