Consider a directed graph where the edges are labelled with integer values. In such a graph a path $a \rightarrow b \rightarrow c \rightarrow d$ is valid if the values of the labels of the edges followed strictly increase along the path. I would like to be able to compute standard graph properties taking into account this extra restriction. Have such graphs been considered in the theory literature before?
EDIT: (This should be a comment but it is too long.) There is a simple reduction that follows by replacing each node $A$ by a bipartite graph with indegree($A$) incoming nodes and outdegree($A$) outgoing nodes. We can then connect the relevant incoming nodes to the outgoing nodes that respect the precedence constraints. This would increase the total number of edges by an additive term which is something like the sum of the square of the degrees of the nodes, where $n$ is the number of nodes in the original. Alternatively one can choose a more compact encoding where the nodes in the first half of the bipartite graph are connected in a line and so are the nodes in the second half and the nodes across from the first half to the second just point to the first node with a valid outgoing edge. This reduces the additive expansion factor to something like $n$ times the average degree of the nodes.
Unfortunately, neither reduction preserves crucial properties of the graph. As an example of the problem, if I want to find out if there is a simple path of length $k$ in the original graph, we can't simply look for simple paths in the transformed graphs. The reason is that a simple path in the transformed graph may correspond to a cycle in the original graph. This means that any graph algorithm will have to be modified to take into account which nodes are in fact the same. In particular any algorithm that relies simply on a matrix representation of the graph (or its eigendecomposition) will not work any more.