**4**

votes

**0**answers

32 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 ...

**0**

votes

**1**answer

90 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

**0**answers

86 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 ...

**1**

vote

**0**answers

112 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

**0**answers

142 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

**0**answers

79 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” ...

**7**

votes

**0**answers

328 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

**1**answer

386 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

**1**answer

433 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 ...

**1**

vote

**2**answers

237 views

### Ihara zeta function (graph theory) coefficients using a line graph [closed]

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

**1**answer

124 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

**4**answers

240 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

**1**answer

628 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

**2**answers

140 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$.
...