Acyclic Orientations and Monotonicity in Graphs

M. Edwards1, C.M. Mynhard1
1Department of Mathematics and Statistics University of Victoria, P.O. Box 3060 STN CSC Victoria, BC, CANADA V8W 3R4

Abstract

A maximal directed path in an acyclic orientation of a graph \( G \) is a path \( a_1 \to a_2 \to \cdots \to a_k \) such that \( \text{id}\; a_1 = \text{od}\; a_k = 0 \). The compression of \( G \) is the smallest integer \( k \) such that, for any acyclic orientation of \( G \), there is a maximal directed path of length at most \( k \). We characterize graphs with compression \( 1 \) and \( 2 \) and determine the compression of trees.

Keywords: vertex ordering, acyclically oriented graph, directed path, compression