#### Abstract

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

*u*) be the (open) neighborhood of vertex

*u*∈

*V*(

*G*). Then

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

*u*there is a

*v*∈

*V*(

*G*)\{

*u*} with

*N*(

_{G}*u*) ⊆

*N*(

_{G}*v*). And a graph

*H*is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if

*N*(

_{H}*u*) ≠

*N*(

_{H}*v*) when

*u*≠

*v*, for all

*u*and

*v*∈

*V*(

*H*).

In Porter and Yucas [3] a characterization of *regular* NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to *all* NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected *r*-regular NAS graphs for *r* = 0, 1, . . ., 6.

*.dvi copy*

#### Recommended Citation

McSorley, John P. "Constructing and Classifying Neighborhood Anti-Sperner Graphs." (Dec 2008).

## Comments

Published in

Discrete Mathematics, 308(23), 5428-5445. doi: 10.1016/j.disc.2007.10.005