4
$\begingroup$

Does the following class of graphs have a name?

I'm interested in directed graphs with the following property: for every cycle (of the underlying undirected graph) half of the edges go in one direction and half in the other direction.

More formally, let $\vec{G}$ be a directed graph and $G$ the corresponding undirected graph. Take any cycle $c$ of $G$ and direct all edges of $c$ in the same direction along the cycle. Then half of the edges in $c$ will match the direction of the corresponding edges in $\vec{G}$ but half will not.

Here is another way of describing the same class of graphs. Let's measure the distance between two vertices $u$ and $v$ as follows: choose any path $p$ (ignoring edge directions) between $u$ and $v$ and let $$\begin{align} d(u,v) :&=(\text{# edges on the path $p$ pointing towards $v$})\\ &-(\text{# edges on the path $p$ pointing towards $u$}) \end{align}$$ I'm interested in graphs where this quantity is independent of the chosen path $p$ between $u$ and $v$.

Yet another way of describing such graphs is the following: it is possible to assign integers to the vertices of the graph in such a way that for every directed edge the assigned number increases by one as we go in the direction of the edge (and decreases by one if we go in the opposite direction).

Note that all cycles in such graphs must have even length. Also, such graphs are acyclic (i.e., DAG) since any directed cycle would violate the half/half requirement.

A simple example of the kind of graph I'm talking about is a 2D square lattice where all horizontal edges are oriented from left to right and all vertical edges are oriented from bottom to top.

$\endgroup$

3 Answers 3

3
$\begingroup$

Yes, these are known as graded graphs.

(This terminology is used in Bela Bollobas's Modern Graph Theory, inter alia.)

$\endgroup$
1
2
$\begingroup$

In network-flow land, this is a "layered network", see for example this (page 114). Unfortunately, that name is used for lots of things.

$\endgroup$
0
$\begingroup$

I would say that these are exactly the graphs which admit a homomorphic image of the form $\bullet\to\bullet\to\dots\to\bullet$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.