2
$\begingroup$

I'm working on a digraph problem in which bidirectional edges need to be treated separately. As such, we could consider them as undirected edges. Clearly, if I replace bidirectional edges with undirected edges I get a ``mixed graph'' (one with directed and undirected edges). But can a mixed graph have bidirectional edges in addition to undirected edges? Can a mixed graph have a directed edge and an undirected edge between two vertices?

The Wikipedia definition is not crystal clear on this. A paper, Enumeration of Mixed Graphs indicates bidirectional and parallel mixed edges are disallowed. The definition in this article claims that the ``complete mixed graph'' has a undirected and bidirectional edge between both vertices.

What are ``mixed graphs'' typically defined as?

1 Answers 1

2

It was always my impression that a mixed graph was graph where some edges were directional and others non-directional. There are directional and non-directional graphs, so logically, a mixed would contain both?

Also, I always thought bidirectional edges are the SAME as undirected edges, as undirected edges mean you can go either way, there are not restrictions. I think it's just semantics. If you have all your other nodes connected by directional edges, then a bidirectional edge for one exclusive set of two nodes is just logical.