Time-stamped graphs and their associated influence digraphs

NEW

Problem: Reconstructed statement: for a path $P_n$, determine all possible values

where $\tau$ is a bijective time-stamping of the $n-1$ edges and $I(P_n,\tau)$ has an arc $u\to v$ iff the unique $u$-to-$v$ path has strictly increasing edge times in that direction. Loops are not counted. This is the natural reading of “values attained from paths” in the paper’s terminology.

Result: Let $m=n-1$. For $n\ge2$, the exact set of attainable values is

with the empty composition allowed when $m=1$, giving $\mathcal V(P_2)=\{2\}$.

Proof. Write the edge labels of $P_n$, in path order, as a permutation

Each adjacent vertex-pair contributes both directed arcs, hence $2m$ arcs.

For vertices at distance at least $2$, corresponding to an interval

there is a left-to-right influence arc exactly when this interval is strictly increasing, and a right-to-left arc exactly when it is strictly decreasing. Thus extra arcs are precisely monotone edge-intervals of length at least $2$.

Let

A length-$\ge2$ edge interval is monotone iff the corresponding consecutive signs are all equal. If the maximal runs of equal signs have lengths $r_1,\dots,r_k$, then a run of length $r$ contains

such sign intervals. Hence

Conversely, given any composition $r_1+\cdots+r_k=m-1$, choose a sign sequence with alternating maximal runs of those lengths. This sign pattern is realized by some permutation: impose inequalities $a_i<a_{i+1}$ for $+$ and $a_i>a_{i+1}$ for $-$. The resulting directed constraint graph is an orientation of a path, hence acyclic, so a topological ordering gives distinct labels $1,\dots,m$ realizing the pattern. Therefore every displayed value is attained.

Verification audit: $P_2$ gives $2$, $P_3$ gives $5$, and $P_4$ gives $8,9$, matching direct enumeration. If one counts reflexive loops, add $n$ to every value.

Citation: No external resolution used. Original problem source: Eddie Cheng, Jerrold W. Grossman, and Marc J. Lipman, “Time-stamped graphs and their associated influence digraphs,” Discrete Applied Mathematics 128 (2003), 317–335.