✦ LIBER ✦

Enumeration and generation of a class of regular digraphs

✍ Scribed by M. V. S. Ramanath; T. R. Walsh

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 346 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110404

No coin nor oath required. For personal study only.

✦ Synopsis

We study the class of directed graphs that have indegree = outdegree = 2 a t every vertex. These digraphs can be decomposed uniquely into "alternating cycles"; w e use this decomposition to present efficient techniques for counting and generating them. The number (up to isomorphism) of these digraphs and the number of connected ones on up to 20 vertices have been computed and are presented.

📜 SIMILAR VOLUMES

Digraphical Regular Representations of I

Digraphical Regular Representations of Infinite Finitely Generated Groups

✍ R.G. Möller; N. Seifter 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 104 KB

A directed Cayley graph X is called a digraphical regular representation (DRR) of a group G if the automorphism group of X acts regularly on X . Let S be a finite generating set of the infinite cyclic group Z. We show that a directed Cayley graph X (Z, S) is a DRR of Z if and only if As a general r

On a Class of Recursively Enumerable Set

On a Class of Recursively Enumerable Sets

✍ Farzad Didehvar 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

## Abstract We define a class of so‐called ∑(__n__)‐sets as a natural closure of recursively enumerable sets __W__~n~ under the relation “∈” and study its properties.

A class of Hamiltonian regular graphs

✍ Paul Erdös; Arthur M. Hobbs 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 317 KB

## Abstract In this paper, we show that __n__ ⩾ 4 and if __G__ is a 2‐connected graph with 2__n__ or 2__n__−1 vertices which is regular of degree __n__−2, then __G__ is Hamiltonian if and only if __G__ is not the Petersen graph.

Computer enumeration and generation of p

Computer enumeration and generation of physical trees

✍ J. V. Knop; W. R. Müller; K. Szymanski; H. W. Kroto; N. Trinajstić 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

A computer-oriented method for the enumeration and generation of physical trees is presented. Physical trees depict acyclic chemical structures, but the term physical is used to stress the process by which the structures are produced.

A class of self-complementary vertex-tra

A class of self-complementary vertex-transitive digraphs

✍ Gek-Ling Chia; Chong-Keang Lim 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) selfcomplementary ver

Asymptotic enumeration of tournaments wi

Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph

✍ Zhicheng Gao; Brendan D. McKay; Xiaoji Wang 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

This paper studies the probability that a random tournament with specified score sequence contains a specified subgraph. The exact asymptotic value is found in the case that the scores are not too far from regular and the subgraph is not too large. An ndimensional saddle-point method is used. As a s