Enumeration and generation of a class of regular digraphs.

*(English)*Zbl 0652.05020Let \(G=(V,A)\) be a finite digraph; and \(X\subseteq A\) is called an alternating cycle (ac) iff its arcs can be ordered as \(e_ 0,e_ 1,...,e_{2r-1}\) such that \(e_ i\) and \(e_{i\oplus 1}\) \((i=0,1,2,...,2r-1\) and \(i\oplus 1\) denotes addition mod 2r) have a common end-vertex which is called exit-vertex of X (start-vertex which is called entry-vertex of X) if i is even (odd), whereby loops are allowed but not parallel arcs. In the present article is studied the class of those regular digraphs, whose vertices all have indegree \(=\) outdegree \(=2\), these are the so-called 2-diregular digraphs (2-dds). It is known that a 2-dd can be uniquely decomposed into acs in linear time, and by using this property it is developed an interesting enumeration formulae for 2-dds and an algorithm to generate them efficiently.

Let be \(A=\{X_ 1,X_ 2,...,X_ k\}^ a \)collection of vertex- disjoint simple acs of G. It is introduced a bijection from the set of entry-vertices of some \(X_ i\) into set of exit-vertices of some \(X_ i\) and in the set of all these bijections is defined the following equivalence relation: two bijections are equivalent iff they yield isomorphic 2-dds, and a partial order. In the article is shown that it suffices to consider the simple acs into which any 2-dd can be split and the given bijections. By using many known results the authors get the number of nonisomorphic 2-dds and from this the number of nonisomorphic connected 2-dds. The computations for these with up to 20 vertices were done on a computer.

In a last chapter the generation procedure which uses a backtracking procedure for generating permutations in lexicographic order is described in 3 steps. Also by using a computer programming 2-dds have been considered with up to 11 vertices.

Let be \(A=\{X_ 1,X_ 2,...,X_ k\}^ a \)collection of vertex- disjoint simple acs of G. It is introduced a bijection from the set of entry-vertices of some \(X_ i\) into set of exit-vertices of some \(X_ i\) and in the set of all these bijections is defined the following equivalence relation: two bijections are equivalent iff they yield isomorphic 2-dds, and a partial order. In the article is shown that it suffices to consider the simple acs into which any 2-dd can be split and the given bijections. By using many known results the authors get the number of nonisomorphic 2-dds and from this the number of nonisomorphic connected 2-dds. The computations for these with up to 20 vertices were done on a computer.

In a last chapter the generation procedure which uses a backtracking procedure for generating permutations in lexicographic order is described in 3 steps. Also by using a computer programming 2-dds have been considered with up to 11 vertices.

Reviewer: H.-J.Presia

PDF
BibTeX
XML
Cite

\textit{M. V. S. Ramanath} and \textit{T. R. Walsh}, J. Graph Theory 11, No. 4, 471--479 (1987; Zbl 0652.05020)

Full Text:
DOI

##### References:

[1] | Graph Algorithms. Computer Science Press, Rockville, MD (1979) pp. 8–10. |

[2] | and , Graphical Enumeration. Academic Press, New York (1973). |

[3] | Irving, Comp. J. 27 pp 373– (1984) |

[4] | Ramanath, J. Graph Theory 9 pp 161– (1985) |

[5] | and , Enumeration and generation of a class of regular digraphs. Technical Report #147, University of Western Ontario, Canada (1986). |

[6] | Trotter, J. Graph Theory 2 pp 137– (1978) |

[7] | Graphs, Groups and Surfaces. American Elsevier, New York (1973) pp. 21–33. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.