Published in Australasian Journal of Combinatorics, 38, 63-76


For a simple graph G let NG[u] denote the closed-neighborhood of vertex uV (G). Then G is closed-neighborhood anti-Sperner (CNAS) if for every u there is a vV (G)\{u} with NG [u] ⊆ NG [v] and a graph H is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if NH[u] ≠ NH[v] when uv, for all u and vV (H).

In this paper we are mainly concerned with constructing CNAS graphs. We construct a family of connected CNAS graphs with n vertices for each fixed n ≥ 2. We list all connected CNAS graphs with ≤ 6 vertices, and find the smallest connected CNAS graph that lies outside these families. We indicate how some CNAS graphs can be constructed from a related type of graph, called a NAS graph. Finally, we present an algorithm to construct all CNAS graphs on a fixed number of vertices from labelled CND graphs on fewer vertices.

cnasAFIN.dvi (78 kB)
.dvi copy