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

**0**

votes

**0**answers

58 views

### Standard terminology for morphisms of binary relations

Dealing with relations in a set theoretic context, i.e. as just sets of ordered pairs what would one call a function $f:\text{fld}(R)\to\text{fld}(L)$ for any relations $R$ and $L$ in each of these ...

**3**

votes

**2**answers

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

**0**

votes

**0**answers

23 views

### Dependencies for directed graphical models with both probabilistic and deterministic nodes

Based on new developments of variational Bayes recurrent neural networks, I have a question about dependencies over latent variables. I have no problems when there are no deterministic nodes. I can ...

**3**

votes

**1**answer

86 views

### an inverse semigroup (and perhaps a $C^*\!$-algebra) associated with a directed graph

The following inverse semigroup associated to a directed graph came up in my research. I've read that from an inverse semigroup one may derive a $C^*\!$-algebra whose generators are partial isometries ...

**3**

votes

**2**answers

88 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)...

**4**

votes

**0**answers

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

**0**

votes

**1**answer

48 views

### Orientations in connected bridgeless graphs

Let $n\geq 3$ be an integer, set $[n] = \{1,\ldots,n\}$ and let $G=([n],E)$ be an undirected connected bridgeless graph. Is there an orientation (explanation below) of $G$ such that for all $a\neq b\...

**3**

votes

**1**answer

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

**1**

vote

**1**answer

79 views

### Sum-coloring a tournament

If $G=(V,E)$ is a loopless finite directed graph and $v\in V$, we set $\text{In}(v) = \{(w,v): w\in V \land (w,v) \in E\}$.
Let $T=(V,E)$ be a tournament such that for every $v\in V$ the set $\text{...

**0**

votes

**0**answers

55 views

### Finding or constraining “last common ancestors” in digraphs

Fix an unweighted, weakly connected digraph $\Gamma$, possibly with loops, and of bounded degree.
Call $p$ a common $n$-ancestor of $q_0,q_1$ if there are $n$-paths (directed paths of length exactly $...

**6**

votes

**1**answer

71 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

**2**answers

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

**4**

votes

**2**answers

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

**0**

votes

**1**answer

104 views

### Length of longest directed circuit in random tournament

Build a random tournament $T=(V,E)$ on $V=\{1,\ldots, n\}$ in the following fashion: for $i < j\in \{1,\ldots, n\}$ let the probability be $0.5$ whether $(i,j)\in E$ or $(j,i)\in E$ (in a ...

**3**

votes

**1**answer

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

**1**

vote

**0**answers

91 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, ...

**6**

votes

**4**answers

720 views

### Minimum negative eigenvalue of zero-one matrices

The following question must have been answered decades ago.
For $n$ fixed, what is the most negative eigenvalue among all trace zero zero-one matrices (that is, all entries are either zero or one, ...

**4**

votes

**1**answer

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

**3**

votes

**1**answer

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

**4**

votes

**3**answers

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

**7**

votes

**1**answer

746 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 [...

**5**

votes

**1**answer

205 views

### Directed homotopy in the Cayley graph of a monoid

There is a the notion of the Cayley graph $C(G)$ of a group $G$ (which depends on a given presentation $G \cong \mathcal F(S) / \sigma$ where $\mathcal F$ is the free group functor and $\sigma$ some ...

**9**

votes

**1**answer

159 views

### A generalisation of $C_0$-semigroups

A $C_0$-semigroup is a strongly continuous family $\{T(t)\}$ of bounded linear operators on a normed space $X$, indexed in $\mathbb R_+$ and with two additional properties that make it look like an ...

**3**

votes

**0**answers

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

**5**

votes

**0**answers

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

**4**

votes

**1**answer

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

**0**

votes

**1**answer

210 views

### Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

211 views

### Inverse (in)degree of a digraph

Hi All,
here is my question. I'm given a directed graph $(V,E)$ with $|V| = n$ vertices and in-degrees $d_1$, $d_2$ ... $d_n$ (so that $\sum_i d_i = |E|$). Can we upper bound the inverse (in)degree ...

**0**

votes

**0**answers

87 views

### “Box Nodes” in Directed Graphs with Paired IO Symmetry

Consider directed graphs where all nodes have 2 inputs and 2 outputs. If we
design a box with N inputs and N outputs, what is the smallest number of
nodes it must contain to satisfy “pair symmetry” (...

**12**

votes

**0**answers

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

**1**

vote

**1**answer

707 views

### Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...

**0**

votes

**1**answer

916 views

### Minimum number of edges - directed graph with given sums of weights

Let's consider a directed graph with positive edge weights. For every vertex we determine the difference
D = (summary weight of edges directed FROM this vertex)-(summary weight of edges directed ...

**1**

vote

**2**answers

305 views

### Ihara zeta function (graph theory) coefficients using a line graph [closed]

I'VE COMPLETELY REVISED MY QUESTION
I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of ...

**5**

votes

**1**answer

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

**5**

votes

**4**answers

298 views

### Majority vote of total orders

Fix an odd natural number $k$. Suppose we have $k$ total orders on the same (finite) set $X$. Define a tournament on the vertex set $X$ by putting a directed edge $x\rightarrow y$ if a majority of ...

**7**

votes

**1**answer

1k views

### Algebraic characterisation of directed acyclic graphs

Any characterization based on the adjacency matrix for directed acyclic graphs (DAG)?
An undirected graph could be simply characterized by saying that its adjacency matrix is symmetric. What about a ...

**1**

vote

**2**answers

189 views

### Is number of quasi-kernels NP-hard?

A quasi-kernel in a directed graph D is an independent subset of vertices $S$ so that for every $v \in V(D)-S$ either $v->s$ for some $s \in S$ or $v->w->s$ for some $w \in V(D)-S, s \in S$.
...