\begin{abstract} Determining order relationship between events in distributed computations is a fundamental problem with applications in distributed monitoring systems and fault-tolerance. Fidge and Mattern's vector clocks capture the order relationship with vectors of size $N$ in a system with $N$ processes. Since many distributed applications use {\em synchronous} messages, it is natural to ask if the overhead can be reduced for these applications. In this paper, we present a new method of timestamping messages and events in synchronous computations that capture the order relationship with vectors of size less than or equal to the size of the vertex cover of the communication topology of the system. Our method is fundamentally different from that of Fidge and Mattern's technique. The timestamps in our method do not use one component per process but still guarantee that the order relationship is captured accurately. Our algorithm is online and only requires piggybacking of timestamps on program messages. It is applicable to all programs that either use programming languages which use synchronous communication such as CSP, or use synchronous remote procedure calls. \punt{Since the size of our timestamps is dependent upon the size of edge decomposition of the communication topology, we give an algorithm that returns an edge decomposition which is optimal for acyclic graphs and at most twice the size of the optimal edge decomposition for general graphs. We also present an offline algorithm and show that timestamping of messages does not take more than $N/2$ components for any synchronous computation. This result is derived using dimension theory of posets. } \end{abstract} %\begin{keywords} %Synchronous Communication, Vector Clocks, Vertex Cover, Dimension Theory. %\end{keywords}