# Questions tagged [directed-graphs]

For questions about directed graphs. In a directed graph, each edge is an ordered pair of vertices; we think of it as pointing from one to the other. Use with the (graph-theory) tag.

224 questions
Filter by
Sorted by
Tagged with
16 views

### Trasitivity of maximum flow

$G=(V,E)$ is a directed graph, $C(e)>0$ for all edges. Is the following correct? For every $3$ vertices, $u,v,w$, if the max flow from $u$ to $w$ is more than $1000$ and the max flow from $w$ ...
16 views

### Complement of the directed graph

What is a formal way to define a complement of a directed graph? On the wikipedia link -> Here it is not quite clear for me if we take the edges of the opposite direction. In any case, could anyone ...
14 views

### Construction of $R$-graph from a directed graph

Let $G$ be a finite directed graph with vertex set $V$ and an edge set $E$. In this paper https://arxiv.org/pdf/1209.2578.pdf, another graph is constructed from $G$ called $R$-graph by the following ...
34 views

### A binary relation contained in its square

My colleague (I guess, investigating structure of specific semigroups) is looking for references about binary relations $R\subset X\times X$ such that $R\subset R\circ R$, that is for each $(v,u)\in R$...
23 views

### chromatic number in directed graphs

the chromatic number in directed graphs $χ_A$(D) is defined as the smallest integer such that there is a coloration without monochromatic directed cycles. it follows that if D is a planar graph, then:...
43 views

### Dificulty to prove chromatic number of directed planar graphs

So I was reading this question and tried to prove it but I don't understand the statements that the answer and comments say since I don't what is a 2-dim sphere and can't understand why $D$ can be ...
17 views

10 views

### For a directed graph with vertex set $X$, why are the arcs members of $X\times X$?

A directed graph G is defined to be pair $(X,U)$ where a. $X$ is a set $(x_1, x_2, x_n,..., x_n)$ of elements called vertices; and b. $U$ is a set $(u_1, u_2, u_3,...,u_n)$ of elements of ...
13 views

### What can be said about the stationary distribution of the Latch Cube?

Katsuhiko Okamoto's Latch Cube is similar to the standard $3\times 3$ Rubik's cube with the added features that on one of the faces of each of the edge cubies, there is an arrow identifying a ...
11 views

### Is there a hash-like function from pointed digraphs where if A and B differ only in the placement of the point, this is clear in the hash?

I want a cryptographically secure hash-like function (it need not output integers, it could be any data type) which takes directed graphs with a single marked point as input, so that if graphs A and B ...
18 views

### Graph Theory - Finding strongly connected components in a directed graph

I am trying to find in the following graph the strongly connected components but i have some questions since in the class we picked up on the topic very briefly. Are loops considered in this example ...
31 views

### Is a directed complete graph Hamiltonian? (if there are no sink groups)

For some graph G that is complete (Kn) and directed (every edge ab can be traversed in only one way, either a -> b, or b -> a) and has no sink groups. Is G necessarily Hamiltonian? If so why? Define ...
33 views

### Help proving a theorem about node ordering of a directed multigraph

We a have polytree $G = (V, E)$. Note that every vertice $v_i$ can only have one outgoing edge. Now lets add a new type of edge which we call an red edge. $R$ is the set of all these edges. So we ...
17 views

22 views

19 views

### squared matrix of a graph?

I am new to graph theory, I am working with DAGs. I came across this code, that when working with 3 nodes it did: dag2=dag2+(dag %^% 2) When it had 4 nodes: <...
30 views

### Finding all subgraphs of DAG connecting source $j$ with sink $i$

Having a directed acyclic graph $G$ with $n$ sources and $m$ sinks what is the (worst case) computational complexity of finding all subgraphs connecting a single source $j$ with a single sink $i$? ...
54 views

### Unlabeled (list-improper) coloring of all directed acyclic graphs with N nodes? (“Distinct Conversations”)

I am attempting to determine the number of distinct possible directed graphs (conversations) with N nodes (statements) colored with P colors (P people conversing.) (This seems to be the number of list-...
47 views

### length of a path that passes through at least one vertex of each (elementary) circuit of a strong connected directed graph

Let $G$ be strongly connected directed graph with vertex set $\{1, 2, \ldots, n\}$. A circuit $i_0=i, i_1, \ldots, i_n=i$ is elementary if path $i_1, \ldots, i_{n-1}$ is a path in which no vertex ...
22 views

### elementary circuit in a strongly connected directed graph

Let $G$ be strongly connected directed graph with vertex set $\{1, 2, \ldots, n\}$. A circuit $i_0=i, i_1, \ldots, i_n=i$ is elementary if path $i_1, \ldots, i_{n-1}$ is a path in which no vertex ...
27 views

### Prove that a subgraph of a de Bruijn graph is still connected

I'm trying to prove the following: consider the de Bruijn graph $$G(2,n)$$ I'm trying to prove that for $$n \geq 4$$ if I remove the vertices $$v_1 = 00..0, v_2 = 11..1$$ and all the edges that ...
136 views

### Counting directed bicliques using Burnside's lemma

Let $b_{n}$ be the number of different directed $K_{n,n}$ graphs, assuming that $G$ and $H$ are considered identical when $G$ is isomorphic either with $H$ or with its transpose $H^T$ (i.e. same graph ...
33 views

### Directed graph with $15$ edges and $16$ nodes

Does this kind of graph have a name other than it is an directed graph? Does it have a property or characteristics? Visually I see $15$ edges and $16$ nodes. I want to learn more about graphs, but ...
136 views

### Confusion about the definition of an acyclic graph

My textbook says Definition 1: A graph, G, is acyclic if it contains no undirected cycles (otherwise it’s cyclic). It also says Definition 2: A (directed) cycle is a (directed) path which ...
65 views

### Number of acyclic digraphs (DAGs) with n labelled nodes and r arcs

I am trying to find a way to calculate the number of acyclic digraphs with $n$ labelled nodes and $r$ arcs. In his paper, Robinson defined a counting function for acyclic digraphs and on the final ...
39 views

### Optimization Problem: Find a smallest $S$ subset of Vertex set $V$ of digraph D

Given a directed graph $D=(A,V)$ , find a smallest set $S\subseteq V$ which satisfies that for every vertex $v\in V$ there exists a vertex $s\in S$ such that there is a directed path from $s$ to $v$ ...
21 views

### Reversing a directed graph preserves acyclicness?

Suppose we have an arbitrary directed graph $G$. We create a related new graph $G'$ by reversing every edge in $G$. Is this statement true or false?: $G$ is acyclic if and only if $G'$ is acyclic.
22 views

### Find Nearest Common Ancestors of two vertices in a directed acyclic graph

I have a hierarchy of nodes that I need to use for an analysis. Sort of like this enter image description here I'm trying to find an algorithm that will allow me to find the nearest common ancestors ...
45 views

### The maximum number of vertices of a directed complete graph that does not contain any totally-ordered $a$-clique and does not contain $b$ triangles

If $a$ and $b$ are positive integers, what is the largest number of vertices that a complete directed graph $G$ can have while not containing any totally ordered $a$-clique and not containing $b$ edge-...
19 views

### Given a directed graph with 3 nodes, where order of nodes dnm, how many graphs are possible?

No nodes have self referencing arrows. I tried solving on paper and got 14 graphs. 2 with 2 arrows, 4 with 3 arrows, 5 with 4 arrows, and 2 with 5 arrows, and 1 with 6 arrows. With 2 arrows: 1 ...
125 views

### Weak and Strong components of graph

I have a graph: I have in my homework assignament that it has 2 weak and 2 strong connected components. I clearly see strong components {4,5} and {0..3} But why they are also weak components if we ...
50 views

### How to maximize the number of edge under no circle in a directed graph?

Here is the question: Assuming a set of node n1,n2,...,nk, each node has some redundant resources represented by a set of numbers. For example, node n1 has resource {1,1,3,6,6,6,9}. And each node ...
30 views

### Eccentricity in infinite tournaments

Definitions. A tournament is an oriented complete graph, that is, it's what you get by taking a (finite or infinite) complete graph and assigning a unique direction to each edge. If $T$ is a ...
Assume there are $n$ vertices, every pair of vertices is connected by an arrow. Then how many directed triangles (for example{ $(1,2),(2,3),(3,1)$})does a graph of this type contain at most?