DFS code and Minimum DFS code

Edge Code

We represent each code e={start, end} with start and end as the starting and ending nodes of edge. The edge code is defined as:

where the Index of a vertex is an arbitrary number, in sequential visiting order, given to the vertices in the graph. The numbers marked in red in the following graph are the indices of the vertices.

There are many edge codes for this graph:

Forward edge: {0,1,X,a,Y}, {1,2,Y,b,X}, {2,3,X,c,Z}, {1,4,Y,d,Z}

Backward edge: {3,1,Z,b,Y}, {2,0,X,a,Z}

It is clear to see that we have for forward edges and  for backward edges.

The order of edges and DFS code

Suppose we have two edges

To determine the ordering between 2 edges we must consider: i) the types of the edges, ii) the visiting order (Index) of the nodes in each edge.

If and are both forward edges, then if one of the following holds:

1. 
2. and

If and are both backward edges, then  if one of the following holds:

1. 
2. and

If  and are one forward edge and one backward edge, then  if one of the following two holds:

1. is forward edge and is backward edge and
2. is backward edge and is forward edge and

The DFS code is just the concatenation of all the edge codes in order. i.e. the DFS code for the above DFS tree is:

{0,1,X,a,Y,1,2,Y,b,X,2,0,X,a,X,2,3,X,c,Z,3,1,Z,b,Y,1,4,Y,d,Z}.

DFS Lexicographic Order and Minimum DFS code

The DFS lexicographic order of the DFS code is defined as follows:

If we have two DFS codes and

then if and only if either of the following is true

1. and

2. and

So we can order a list of DFS codes according to the DFS lexicographic order, and we define a minimum DFS code as the minimum one among all the possible DFS codes of a graph.