A directed graph is a graph with directed edges. Loops and 2-cycles are usually allowed. See also the tag *quiver*.

learn more… | top users | synonyms

-3
votes
0answers
25 views

Calculate minimal number of nodes? [on hold]

Calculate minimal number of nodes? in a loopless simple undirected pi-partite graph. that has exacatly 144 nodes
-3
votes
0answers
27 views

Directed and undriected trees [on hold]

How many different directed trees can be obtained if we assign all possible orientation to the edges of an undirected tree having exactly 7 nodes? how many of them will be rooted(directed) trees?
0
votes
0answers
33 views

Determine number of directed trees and rooted trees obtainable [on hold]

I've been doing some exercices about graph theory and I find myself stuck on this one with no idea of to proceed. Here's the question : how many different directed trees can be obtained if we assign ...
0
votes
0answers
26 views

adjacent matrix directed or undirected [on hold]

I'm having trouble seeing how you can determine if a graph is directed or directed based off of the adjacent matrix. Can someone explain to me how to determine ths? Thanks!
1
vote
0answers
102 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
104 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
72 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” ...
6
votes
0answers
250 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
1answer
266 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
1answer
226 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 ...
0
votes
2answers
182 views

Ihara zeta function (graph theory) coefficients using a line graph

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
1answer
113 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
4answers
201 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 ...
4
votes
1answer
398 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
2answers
121 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$. ...