Adjoints of pure bidirected graphs. (English) Zbl 0537.05024
Combinatorics, graph theory and computing, Proc. 14th Southeast. Conf., Boca Raton/Flo. 1983, Congr. Numerantium 39, 123-144 (1983).
[For the entire collection see Zbl 0523.00001.]
A graph G is called bidirected if each edge has a direction associated with each of its endpoints. Let u be an edge, x be an endpoint of u. If the direction associated with u and x is towards x then x is a head of u, and if it is away from x then x is a tail of u. If edges u and v have a common endpoint y, then we say that v follows u if y is a head of u and a tail of v. A bidirected graph G is called pure if no edge of G has two tails. The adjoint \(G^*\) of G is the directed graph whose vertices are the edges of G, and where there is an arc from u to v if and only if v follows u in G. In the paper, the adjoints of pure bidirected graphs are characterized by forbidden subgraphs.
A graph G is called bidirected if each edge has a direction associated with each of its endpoints. Let u be an edge, x be an endpoint of u. If the direction associated with u and x is towards x then x is a head of u, and if it is away from x then x is a tail of u. If edges u and v have a common endpoint y, then we say that v follows u if y is a head of u and a tail of v. A bidirected graph G is called pure if no edge of G has two tails. The adjoint \(G^*\) of G is the directed graph whose vertices are the edges of G, and where there is an arc from u to v if and only if v follows u in G. In the paper, the adjoints of pure bidirected graphs are characterized by forbidden subgraphs.
Reviewer: F.Tian
