Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
16 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 ...
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 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 $...
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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^...
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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) &...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$, ...
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 ...
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 ...
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 — ...
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 ...
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 ...
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, ...
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 ...
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 ...