The book from which I am studying graph theory has this definition of a covering edge:
If $a$ and $b$ are distinct nodes of a digraph, then $a$ is said to cover $b$ if there is an edge from $a$ to $b$ and every path from $a$ to $b$ includes this edge. If $a$ covers $b$, the edge from $a$ to $b$ is called a covering edge.
From what I understand from this definition, $a$ is said to cover $b$ if:
- There is an edge from $a$ to $b$
- There is only $1$ path from $a$ to $b$. (Since any other path from $a$ to $b$ would not traverse this edge.)
If I am right, then the covering edges of this DAG would be {($1$,$2$),($1$,$3$),($1$,$5$),($2$,$4$),($2$,$6$),($3$,$6$)}.
Am I correct? If not, then what should be the covering edges in this digraph?
Yes, your solution is correct. To put the definition a little bit differently: If $a$ covers $b$, then there is no longer path between $a$ and $b$ other than the edge itself. For example, $1$ does not cover $6$ because the path $1-3-6$ exists.
I provide some extras that are quite useful.
We can easily derive this simple relationship from the above:
If there is a path between vertices $a$ and $b$, then there exists a path from $a$ to $b$ which only contains covering edges.
First, observe that if there exists a path between $a$ and $b$, then there is a longest one. Suppose that there is no path between $a$ and $b$ that does not only contain covering edges. Let $P$ be the longest path between $a$ and $b$. Suppose that this path does contain a non-covering edge, say $(x,b)$, then there must be a path $x - x' - \cdots - b$ in the graph. But then $P$ would not be the longest path. A contradiction.
Consider this figure (excuse my poor drawing)
For example, there are two paths from $1$ to $6$ which only contain covering edges, e.g. $1-2-6$ and $1-3-6$ and $1-6$ is not a covering edge.
Hence, the covering edges of the graph are contained in the longest paths of all pairs of distinct vertices of the graph. The paths $1-2-6$, $1-2-4$, $1-3-6$ and $1-5$ encode all covering edges.