All Questions
10 questions
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 ...
- 121
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
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
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
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
1
vote
1
answer
216
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
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
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
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
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