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 …

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 satis …

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 indegr …

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 res …

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 o …

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 d …

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 spanni …

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 …

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 symme …

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, …