All Questions
33 questions
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
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
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
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
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
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
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
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
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
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
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
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
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
156
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 ...
- 71
2
votes
0
answers
169
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
1
vote
2
answers
198
views
Topology of directed graph $G$ with non-singular adjacency matrix
Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
- 4,058
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
1
vote
1
answer
110
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
1
vote
1
answer
182
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 ...
1
vote
0
answers
145
views
Misunderstanding the definition of kernel in digraphs
By Borodin–Kostochka–Woodall '97 paper, the first paragraph says that directed odd cycles do not have kernels. But, I don't get this. Like, consider any $\lfloor\frac{n}{2}\rfloor$ set of independent ...
- 2,089
1
vote
0
answers
65
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 ...
- 71
1
vote
0
answers
82
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
1
vote
0
answers
108
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 ...
- 2,089
1
vote
0
answers
108
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, ...
- 525
0
votes
0
answers
19
views
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs.
You are given a 2 regular (2-in 2-out) directed graph where you can check that ...
- 41
0
votes
0
answers
51
views
Kernel perfection in some powers of cycles
Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
- 2,089