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.

Filter by
Sorted by
Tagged with
-1
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$...
1
vote
0answers
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:...
3
votes
0answers
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 ...
1
vote
0answers
17 views

Equivalence relation in a simple directed graph $D$

I have written my proof, but I'm still not sure if it's rigth: Determine if for all directed graphs $D$ the following relation $R$ defined in $V(D)$ is an equivalence relation: $xRy$ if and only if $...
0
votes
0answers
11 views

Breadth First Search for Directed Graph

Consider the following graph I was asked to list the nodes of the graph in breath-first traversal, starting from node 0. My result is as follow I'm not sure about the 2 node. What do I do with ...
0
votes
0answers
25 views

Determine if for all directed graphs $D$ the following relation R defined in $V (D)$ is an equivalence relation

Determine if for all directed graphs D the following relation R defined in $V (D)$ is an equivalence relation: $xRy$ if and only if $x = y$ or there is an $xy$-path directed. I don't seem to ...
2
votes
1answer
88 views

Show that if $D$ is a planar directed graph without directed edges going in both ways, then $χA (D) ≤ 3$

I have stuck been with this problem. I know that the chromatic number in a directe graph $χA (D)$ is defined as the smallest integer such that there is a coloration without monochromatic directed ...
0
votes
1answer
33 views

Strongly connected components of this digraph

Consider the following Digraph Identify the strongly-connected components of D, and sketch the associated condensation digraph. My attempt: Since $a \rightarrow b \rightarrow c$ and $e \...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
17 views

Let $D$ be a transitive tournament. Show that there is an order $v_1, v_2, …, v_n$ of the vertices of $D$

Let $D$ be a transitive tournament. Show that there is an order $v_1, v_2, ..., v_n$ of the vertices of $D$, such that $d^+(v_i) = n-i$ for all $i = 1,..., n$. My try: Let $v_1 \in V$ such that $d^...
1
vote
1answer
79 views

How can I solve the Rotating Drum problem for 64 segments? (Or at all)

For clarification, I am very bad at maths and the logic usually goes right over my head, however I am studying a reasonably high level of maths because I am a software and game development student. I ...
1
vote
2answers
45 views

Maximal spanning acyclic subgraph

Given a connected undirected graph (in particular as a directed one but with arcs in both ways), my problem is to find a subgraph such that: is a directed acyclic graph is possibly maximal in the ...
2
votes
1answer
25 views

Reference Request: GI Completeness of Directed, Bipartite, Colored Graphs

I have a proof of various gadgets by which I can show that directed, bipartite, vertex colored graphs are graph isomorphism complete. However, I'd rather just cite the result. Can someone give a ...
3
votes
2answers
84 views

If a tournament graph has no cycles of length $3$, prove that it is a partial order.

If a tournament graph has no cycles of length $3$, prove that it is a partial order. I was thinking that perhaps a proof by contradiction might helpful. Could I start with a tournament graph $G$ that ...
1
vote
0answers
125 views

Is there an approximate counting equation for paths in a directed acyclic graph with known average out degree and number of vertices?

If I have a directed acyclic graph (DAG) where I know the average out degree and the exact number of vertices, is there a counting equation to give me the expected number of paths? Edit Thanks for ...
1
vote
1answer
101 views

Every simple directed graph on $n$ vertices contains $2$ vertices with the same indegree or $2$ vertices with the same outdegree.

For each $n \ge 1$ answer true or false: Every simple directed graph on $n$ vertices contains $2$ vertices with the same indegree or $2$ vertices with the same outdegree. Explain your answer in every ...
0
votes
0answers
17 views

show maximum number of arc disjoint directed $s-t$ paths is equal to max flow

Given: $D = (V,A)$ a directed graph and $s,t \in V$ Problem: Show that the maximum number of pairwise arc-disjoint directed $s-t$ paths is equal to the maximum value of the flow $f$ where $f$ is ...
0
votes
0answers
21 views

A question about s-t cuts in graph theory and their reverse.

Let's have a directed graph $G=(V,E)$. If I pick some vertex to be the source $s$ and the some other vertex to be the sink $t$, I can calculate the max flow allowable on the graph from $s$ to $t$ ...
0
votes
0answers
36 views

Graph Theory- tournament bijection [duplicate]

Am trying to find a way to prove: Show that for every tournament $D = (V, A)$ on at least 2 vertices, there is a bijection $π:{1,\dots,|V|} → V$ such that for every $i ∈ \{1,\dots,|V|−1\}$, $\;(π(i)...
0
votes
1answer
22 views

Shortest Path under 2 different weight functions

Q) Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $...
0
votes
0answers
27 views

Ford Fulkerson MaxFlow dCut

Question is the following: Z={A,B} subset of V containing all Nodes. State dCut({Z}, G). Does the above dCut induce an upper bound to the maximum s – t flow value? If so,what is the induced upper ...
0
votes
0answers
21 views

A question about Boolean Matrix

Let $(\mathbb{B}^{n\times n}, \bigotimes, \bigoplus )$ be Boolean algebra, where $\mathbb{B}^{n\times n}$ is the set of Boolean matrix $A_{n\times n}$. The Boolean matrix power of the matrix $A\in \...
0
votes
0answers
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: <...
0
votes
0answers
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$? ...
0
votes
0answers
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-...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
6
votes
1answer
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$ ...
0
votes
1answer
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.
0
votes
0answers
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 ...
0
votes
0answers
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-...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
2answers
96 views

What is the maximum number of directed triangles contained in an oriented complete graph?

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?
0
votes
1answer
28 views

Using graph theory to find the maximum compatible clique

Imagine a person wants to celebrate his birthday. But some of the guests don't like each other. Person A says she won't come if Person B or Person C is there. Person B and Person D say that they won'...

1
2 3 4 5