𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Asymptotic enumeration of full graphs

✍ Scribed by D. J. Kleitman; F. R. Lasaga; L. J. Cowen

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
539 KB
Volume
20
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets, and a directed edge from a to b if the corresponding set A contaisn B. We give a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph in the n vertices, distinguishing a clique in this graph that need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. Β© 1996 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

Asymptotic Enumeration of Convex Polygon
Asymptotic Enumeration of Convex Polygons
✍ Dudley Stark; Nicholas C. Wormald πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 413 KB

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice Z d taking at least one step in every dimension. A polygon on Z d is said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number of d-dimensional convex pol

Enumeration of connected graph coverings
Enumeration of connected graph coverings
✍ Kwak, Jin Ho; Lee, Jaeun πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 207 KB πŸ‘ 1 views

The number of the isomorphism classes of n-fold coverings of a graph G is enumerated by the authors (Canad.

Enumeration of Cubic Graphs by Inclusion
Enumeration of Cubic Graphs by Inclusion–Exclusion
✍ William Y.C. Chen; James D. Louck πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 92 KB

We use the principle of inclusion and exclusion to enumerate labeled cubic graphs, without resort to the superposition theory of Read. This work was motivated by the cubic array representation of cubic graphs in the studies of generating functions of 3n& j coefficients in angular momentum theory.

Computer enumeration of walks on directe
Computer enumeration of walks on directed graphs
✍ K. Balasubramanian πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 526 KB

A vectorized computer code is developed for the enumeration of walks through the matrix power method for directed graphs. Application of this code to several graphs is considered. It is shown that the coefficients in the generating functions for signed graphs are much smaller in magnitude. It is sho