Abstract
Properties of (connected) graphs whose closed or open neighborhood families are Sperner, anti-Sperner, distinct or none of the proceeding have been extensively examined. In this paper we examine 24 properties of the neighborhood family of a graph. We give asymptotic formulas for the number of (connected) labelled graphs for 12 of these properties. For the other 12 properties, we give bounds for the number of such graphs. We also determine the status (a.a.s. or a.a.n.) in Gn,1/2 of all 24 of these properties. Our methods are both constructive and probabilistic.
Recommended Citation
Clark, Lane, Holliday, Sarah, McSorley, John and Porter, Thomas. "ENUMERATING LABELLED GRAPHS WITH CERTAIN NEIGHBORHOOD PROPERTIES." Congressus Numerantium 190 (Jan 2008): 193-206.