Enumeration of Full Graphs: Onset of the Asymptotic Region

Publisher: John Wiley & Sons Inc

E-ISSN: 1467-9590|96|3|339-350

ISSN: 0022-2526

Source: STUDIES IN APPLIED MATHEMATICS, Vol.96, Iss.3, 1996-04, pp. : 339-350

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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 contains B;. Kleitman, Lasaga, and Cowen gave a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph on the n vertices, distinguishing a clique in this graph, which 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. Call graphs of this type members of the dominant class. This article obtains the first upper and lower bounds on how large n has to be, so that the asymptotic behavior is indeed observed. It is shown that when n > 170, the dominant class predominates, while when n < 17, the full graphs in the dominant class compose less than half of the total number of realizable full graphs on n vertices.