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
3
votes
1answer
147 views

Characterizing relations by forbidden induced subsets

Working with relations in a purely set theoretic manner i.e. as just sets of ordered pairs, we see for any relation $R$ there exists unique inclusion minimal sets $A$ and $B$ such that $R\subseteq A\...
1
vote
2answers
40 views

Finding the max-value set of cycles in a weighted digraph

I am looking for the most efficient algorithm that can solve this problem: Given a directed graph with real-valued edge weights, find a set of directed cycles (no two cycles can share a vertex) that ...
2
votes
0answers
50 views

When does a biconnected graph have a minimally strong orientation?

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...
0
votes
0answers
17 views

Twisted Laplace eigenvalues on graph

Let $X$ be a regular finite connected graph and $\Gamma$ its fundamental group. Fix a character $\chi:\Gamma\to\mathbb{C}^\times$. This defines a locally constant sheaf on $X$ and there is an ...
1
vote
0answers
84 views

Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs. Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that \...
1
vote
1answer
91 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)...
2
votes
1answer
81 views

Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute. Two complex matrices $A$ and $B$ are said to be unitary similar if ...
0
votes
1answer
108 views

Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph

I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they ...
6
votes
0answers
94 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
votes
2answers
113 views

Frobenius normal form of a doubly stochastic matrix

If $A \in M_n(\mathbb{C})$, then $A$ is called reducible if there is a permuation matrix $P$ such that $$ P^\top A P = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}, $$ in ...
1
vote
1answer
92 views

Latent Dirichlet allocation and properties of digamma function

In the paper Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent Dirichlet Allocation. Journal of Machine Learning Research, 3(4–5), 993–1022. http://www.jmlr.org/papers/volume3/blei03a/blei03a....
1
vote
0answers
41 views

Proof of the asymptotic expression for the number of self-converse digraphs?

The following expression was mentioned in the master thesis of Alastair Farrugia on Page 199 of his thesis Self-complementary graphs and generalisations: a comprehensive reference manual, M.Sc. Thesis,...
3
votes
0answers
40 views

Groups that can occur as graph automorphisms of a fixed size graph

From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's ...
3
votes
1answer
32 views

Finite sequences realizable by degree difference in digraphs

Let $n>0$ be an integer, and let $[n] = \{1,\ldots,n\}$. A function $f:[n]\to \mathbb{Z}$ is said to be in- and out-degree-realizable (or io-realizable for short) if there is a directed graph $G = (...
6
votes
1answer
116 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
vote
1answer
60 views

Algorithm generating digraphs

Is there an algorightm generating all digraphs with $n$ edges up to isomorphism whose underlying graph is not a tree? For example, for $n=3$, there are only two such digraphs, representable as $\text{...
2
votes
0answers
165 views

Algorithms for rooted directed acyclic graph isomorphism

Given two directed acyclic graphs $G_1$ and $G_2$, and their roots $r_1$ and $r_2$, is there a polynomial algorithm to determine if $G_1$ and $G_2$ are isomorphic?
3
votes
1answer
214 views

Does every directed graph have a directed coloring with $4$ colors?

Every finite directed graph has a majority coloring with $4$ colors. (The notion of majority coloring is defined below.) Question. Can every infinite directed graph be majority-colored with $4$ ...
3
votes
0answers
68 views

Decreasing the directed chromatic number of a digraph by adding an edge

The chromatic number of an undirected graph can never be decreased by adding an edge. However, things are not that clear when we deal with coloring directed graphs - but first, the definition of this ...
0
votes
1answer
85 views

Name for Directed Edges in Digraphs

Graph theory originated in German speaking countries and there directed edges are called "Pfeil" which translates to "arrow", which makes sense, because arrows have distinguishable front end and rear ...
3
votes
1answer
79 views

Generalized digraph homomorphisms and graph cores

Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...
3
votes
2answers
246 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 ...
3
votes
1answer
92 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
2answers
97 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
0answers
149 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
1answer
54 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
1answer
414 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
1answer
83 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{...
6
votes
1answer
75 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
2answers
222 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
2answers
336 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
1answer
119 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
1answer
548 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
0answers
95 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
4answers
775 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, ...
5
votes
1answer
218 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
1answer
1k 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
3answers
209 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 ...
8
votes
1answer
1k 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
1answer
216 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
1answer
178 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
0answers
104 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
0answers
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 ...
5
votes
1answer
701 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
1answer
229 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
0answers
161 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
0answers
159 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
0answers
221 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
0answers
89 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” (...
14
votes
0answers
512 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 ...