#### Abstract

For a simple graph *G* let *N _{G}*[

*u*] denote the closed-neighborhood of vertex

*u*∈

*V*(

*G*). Then

*G*is closed-neighborhood anti-Sperner (CNAS) if for every

*u*there is a

*v*∈

*V*(

*G*)\{

*u*} with

*N*[

_{G}*u*] ⊆

*N*[

_{G}*v*] and a graph

*H*is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if

*N*[

_{H}*u*] ≠

*N*[

_{H}*v*] when

*u*≠

*v*, for all

*u*and

*v*∈

*V*(

*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.

*.dvi copy*

#### Recommended Citation

McSorley, John P., Marr, Alison, Porter, Thomas D. and Wallis, Walter D. "Closed-Neighborhood Anti-Sperner Graphs." (Jun 2007).

## Comments

Published in

Australasian Journal of Combinatorics, 38, 63-76